I suggest a cookie since it is lightweight. Have a one-time created cookie that is created the first time the user accesses any part of the site (assuming their first time they came from an external site such as google).
So each page would do something like "If cookie does not exist create one with last page visited". Since this would be on every page, it would have to contain some external link (although not neccessarily google).
Then if the user registers, save this information iff it matches certains
patterns. For example, if it contains
www.google.com, its fine to save, but some may contain garbage values or irrevelant link so you just skip those. It should work in 80-90% of the cases the user found you via a search engine. As with most things on the web, nothing is bullet proof.