Is it possible to have a
Lookup column that points to a different SharePoint site, hosted on the same SharePoint server?
A different site yes. A different site collection no. Then you'd need to create your own custom field type. Going to another webapp is another thing altogether (security wise it can be tricky). 1 option could be to move your column to managed metadata if you are using SP2010, or use the BCS.
If you create your lookup column as a Site column, then you can use it in all lists and child sites below that site.
Therefore, if you create a lookup at the site collection root, you will be able to use it everywhere in that site collection.
Sadly, there is no easy way of doing a lookup across site collection boundaries.