It's a built-in app and can't be uninstalled.
To restore the icon to the home screen, find the icon in the application list and long-press, then drop it where you want it. Alternately, long-press the home screen where you want the icon to be, choose "Shortcuts", then "Applications", then the "Market" icon.
Update: Okay, it appears that you're not the only one with this issue. See this thread on the Google support forum: http://www.google.com/support/forum/p/Android%20Market/thread?tid=3322620a3c715568&hl=en
One offered solution is to do a factory reset. It's up to you to decide how comfortable you are with that.
Update 2: Several people in this thread said that the factory reset worked for them. Additionally, someone wrote a script (also in that thread) to fix the issue, which you would need to get on the phone. (USB would seem to be your best bet.) Caveat Emptor. Someone also mentioned that if you get the Vendor.apk you can also get the Market back. (Details are a little fuzzier.)