The cognitivistic paradigm, which states that cognition is a result of computation with symbols that represent the world, has been challenged by many. The opponents have primarily criticized the detachment from direct interaction with the world and pointed to some fundamental problems (for instance the symbol grounding problem). Instead, they emphasized the constitutive role of embodied interaction with the environment. This has motivated the advancement of synthetic methodologies: the phenomenon of interest (cognition) can be studied by building and investigating whole brain-body-environment systems. Our work is centered around a compliant quadruped robot equipped with a multimodal sensory set. In a series of case studies, we investigate the structure of the sensorimotor space that the application of different actions in different environments by the robot brings about. Then, we study how the agent can autonomously abstract the regularities that are induced by the different conditions and use them to improve its behavior. The agent is engaged in path integration, terrain discrimination and gait adaptation, and moving target following tasks. The nature of the tasks forces the robot to leave the ``here-and-now'' time scale of simple reactive stimulus-response behaviors and to learn from its experience, thus creating a ``minimally cognitive'' setting. Solutions to these problems are developed by the agent in a bottom-up fashion. The complete scenarios are then used to illuminate the concepts that are believed to lie at the basis of cognition: sensorimotor contingencies, body schema, and forward internal models. Finally, we discuss how the presented solutions are relevant for applications in robotics, in particular in the area of autonomous model acquisition and adaptation, and, in mobile robots, in dead reckoning and traversability detection.