Using Google Maps, I can't see any connections between Crete and Africa. In fact, I can't find any connections from Greece at all. Why is this?
There are currenty (February 2013) no ferries connecting Egypt with any country on the European mainland, but you may be able to get from Malta to Libya. If confirmed, this means you can travel Greece – Italy – Malta – Libya, but the information on the Malta – Libya link appears unclear. Edit: However, one can get to Tunisia or countries further west, see MarcelC's answer.
This is likely because of the political situation. See, for example, the Egypt page on Seat61:
Then a new weekly ferry service started on 20 May 2010 linking Venice in Italy with Alexandria in Egypt, see www.visemarline.com. However, sorry as I am to be proved right, this service didn't last more than a year - it ran in a circle via Syria, and has fallen victim both to the problems in Egypt reducing tourist numbers and the current problems in Syria. The Visemar service was cancelled from May 2011. So although the Mediterranean is full of useless cruise ships going round in circles, there are now sadly no proper scheduled shipping services at all linking anywhere in Europe with Egypt.
This was a service linking Italy with Egypt. You're asking Greece to Africa in general. From Greece, Egypt would make the most sense. Another possibility would be Libya:
There appears to exist a cargo ferry connecting Malta and Libya that takes passengers: have a look at Mediterraneas Maritime Solutions Ltd. (MMSL): The service operates from Valletta Cruise Port Terminal (next to Valletta Waterfront) to Misurata Port, Libya. I am not sure if this service actually exists, as the website states The service will be operating... even if they should have started in 2011. However, this Maltese page from June 2012 states that Passengers now have a choice of two companies to cross over to the mainland1, and this article from the Times of Malta states that the ferry really exists. In any case, Malta has a ferry connection from Italy, and there are ferries from Greece to Italy.
1From context, I think they mean two companies connection to mainland Europe, including one continuing to Africa
Edit: of course, one can get to other African countries further west: see MarcelC's answer
At this time (February 2013) there is no direct ferry from Greece to Africa. The reason is that there is no demand for such a service. There are plenty of ferry connections between Europe and Northern Africa. For instance, Marseille has convenient connections with Tunisia, Algeria and Morocco. There is a big community with immigrants from these countries in France. And there is trade going on between these countries. Hence there is a demand for such a service. In Spain and Italy you also have such communities, albeit smaller than in France. Spain is geographically close to Morocco and Algeria, and well connected to the North of Europe.
But is there a big demand for a service between Greece and Egypt? Is there a big enough Greek community in Egypt, or a big enough community of Egyptians in Greece? I don't think so. Moreover, the road connections from Northern Europe to Greece are not so good. A ferry from Venice to Egypt, as there has been one (see @gerrit's post), makes more sense. It can capture the demand from the more Northern part in Europe. Venice is well connected to the European road network. Nevertheless, as the situation in Egypt is rather precarious, the demand for such a ferry connection to Egypt is pretty weak.
This being said, it is possible to travel by boat and train from Greece to Morocco or Tunisia via Italy. No need to travel via Malta! There is a company which is running ferries from Civitavecchia to Tunis, Salerno to Tunis and Livorno to Tanger. There is another company operating a ferry between Genova and Tunis.
If you are interested in Tunisia, travel by ferry from Greece to Brindisi or Bari. Take a train to Salerno or Civitavecchia and then the ferry to Tunisia.
If you plan to travel via Genova, you can take a ferry from Greece to Venice and then continue from there by train.
If you are interested in Morocco, you can also travel from Greece to Venice, and then by train from Venice to Livorno.