After doing a little web research and even the Skype website itself, I've reached the following conclusion:-
Apparently, Skype Mobile doesn't support Symbian S60^3 devices any longer so it won't appear there. But if you have installed it before, you'll find it under 'My Stuff' in Ovi Store. Then try this:
1. Uninstall Skype.
2. Restart your phone.
3. Change the date three years earlier. (e.g. July 9, 2011)
4. Ovi Store > My Stuff > Skype > Download.
5. Once installation is done. Restart your phone.
6. Change the date to current date.
7. Open Skype then sign in.
Even though you're with o2, I'm presuming your E63 screen is pretty much set out the same as mine where you have six icons in a row:- Yellow Envelope (Text Messages), Sky, YouTube, Bebo, Facebook and an icon to Switch Mode. If you select this last one, you should then see the Skype icon, which would indicate the app is already installed on your mobile. If so, you should try following the steps above. Hope this helps.
Speaking of which, I think I'm going to have to do the same thing, as my E63 still won't connect to Skype.