Cytoscape has biology awareness, recognizes formats such as SMBL and knows about gene ontology formats and data. The apps developed for Cytoscale are mostly systems biology oriented.
Gephi is a more generic network visualizer that is not targeting any specific use case.
Disclosure: I'm a core developer of Cytoscape
Cytoscape is a de-facto standard in life science research, mainly because of large user community and its Apps. Of course, Gephi has some advantages over Cytoscape, such as nice presets and built-in statistical analysis module and we, Cytoscape core team, is learning from them. If you have feature request which is available in Gephi but not in Cytoscape, please let us know :)
I would highly recommend Cytoscape 3 - it has a much more polished, refined UI, and the new "app store" continues this trend by facilitating simple plugin installation - however, not all plugins are supported by version 3; version 2.8 is still very usable and supports the majority of plugins out there. However, many large datasets I had trouble loading into version 3 were tackled by version 2.8 no problem, I suspect due to visualization improvement requirements.
I have only played around with gephi, and my impressions are exactly what Istvan noted - its intended use for a broader audience makes its use not as straightforward regarding biological data
Disclosure: I am a member of the Gephi community support team.
I agree with what Istvan Albert and keiono have shared. Cytoscape has a much broader ecology of plugins for biological research, for example. One strength of Gephi is that it handles well the visualization of very large, dynamic networks.
Both software keep evolving, so it is worth re-checking their features periodically. If you have any question or feature request for Gephi please use the forum of Gephi (http://forum.gephi.org), post on the Facebook group (https://www.facebook.com/groups/gephi) or give a shout to @gephi on Twitter.