A mobile agent, which is an autonomous device navigating in a graph, has to explore a given graph by visiting all of its nodes. We adopt the (arguably) weakest possible model of such a device: a deterministic memoryless automaton (DMA), i.e., a deterministic automaton with a single state. As expected, such a weak machine is incapable of exploring many graphs without marking nodes. Hence we allow the agent to use identical movable pebbles that can be dropped on nodes or picked from them. It turns out that this marking capability significantly enhances the exploration power of the agent. Our goal is to study how the availability of pebbles impacts the class of graphs that a DMA can explore. We first concentrate on finite graphs and show that any finite tree can be explored by a DMA without pebbles but there exist (small) finite graphs that cannot be explored by a DMA without pebbles. Then we turn attention to infinite graphs and fully characterize the class of infinite trees that can be explored by a DMA without pebbles. We also define a large class of infinite trees that can be explored by a DMA with finitely many pebbles. It turns out that many of these trees cannot be explored by a DMA without pebbles. On the other hand, we show a large class of infinite trees that cannot be explored by a DMA with finitely many pebbles. Thus, availability of pebbles yields a strict hierarchy of difficulty of exploration of infinite graphs by a DMA, and this hierarchy is strict even for the class of infinite trees: some trees can be explored without pebbles, some trees can be explored with finitely many pebbles but not without pebbles, and some trees require infinitely many pebbles. Finally, we consider exploration by a DMA with infinitely many pebbles. It turns out that all infinite trees can be explored by a DMA with infinitely many pebbles. By contrast, we construct infinite graphs that cannot be explored by any DMA, even with infinitely many pebbles.