As dagon suggests, using cookies/sessions to track a user within your website is your only real alternatives.
As to tracking outside referrals (e.g. what site were they at before they visited your website), I really don't think there's any other way of doing this. The only way you can possibly tell what site they came from is if their browser shares this information with you (e.g. the HTTP_REFERER header), though this is, as you say, completely optional and untrustworthy.
