shouldn't be a big deal.. icons in the dock are essentially "shortcuts"...
First, you have to find where the actual program is on your hard drive. Typical place is in the Applications folder. You mentioned you looked there, so you might also look in your home folder. If all else fails, just search for it using spotlight (that blue spy glass icon in the upper-most right corner of your screen).
Once you find the folder it's in, just drag the icon from that folder back to the place in the dock you want the shortcut.
Should do it.