Greece is a famous beach destination, and many island hoppers like to go for a walk now and again. Most islands are quite suitable for hiking, and locally guides and maps are available giving good descriptions of trails. But the crowded summer season is hot and dry. April is a much better month for hiking, with all flowers in full bloom, and also May, although it will start to get busier. June is more quiet but very hot. The busy season then lasts until winter. Although common in the past, your chances of actually following in the footsteps of mules carrying their loads in the traditional manner are dim.
But there is more. If you've had enough of the island's oregano, you can head for the mainland Pindos Mountains in the province of Epirus, on the border with Albania. European long distance trail E6, running from west to east, leads right across the Pindos. In the wide expanse of forests and pastures you may cross tracks with a bear (see the picture of a bear track which caused the author to freeze with fear), or if not, then at least with one or two herdsmen smelling of the inevitable ewe's cheese. Smolikos is the highest peak, reaching up to 2637m. Walking season in the mountains is from May, when the mountain tops are still covered in snow, until mid October. Greek mountain ranges have been made increasingly accessible over the years thanks to over 100 mountain huts.
Make an effort, and find out Greece has almost twenty national trails, maintained by regional mountaineering clubs. European long distance trail E4 enters Northern Greece from Bulgaria, and runs south via Mount Olympus (2918m), highest mountain of Greece and pleasant abode of Zeus. If you plan to spend the night there yourself in July or August, make sure to reserve in advance. The trail then leads across the Peleponessos, leaving it in the south, and continues on the island of Crete. Crete of course is famous for its Samaria gorge, the longest in Europe. It is impossible to lose your way here, simply join the crowd.
The Internet is not yet a very good source of information on Greek hiking, but maps and guides are easy to find. More information can be obtained through the Hellenic Federation of Mountaineering and Climbing.