Maybe the icon is 'hidden'. Search for 'Cydia' (on spotlight). You can use i.e. SBSettings for showing it again on the homescreen.
Otherwise the only way is to rejailbreak your device. But I think you don't have to 'dejailbreak'. Just run the jailbreak again
If Cydia was actually deleted (although I'm not sure how that would have happened), you could resinstall it via SSH (assuming you already had openSSH installed): http://www.ifans.com/forums/showthread.php?t=288899