Do you need Gollum to be in the staging area when finishing the last stage? I couldn't find anywhere in the rules this (can he be lost, shuffled in the encounter deck?)

You need Gollum. The final quest stage has the text "If Gollum is not captured at this time, reset the quest deck to stage 1B." So, if you defeat the last stage and Gollum is not in play, then you have to go back to 1B and continue from there.\

It's really really bad to lose Gollum.

I was literally playing this last night and lost him twice in one game before threading out! In effect, on completion of stage 2B, without Gollum in the staging area, you do an Escape test revealing 0 cards. So as long as you commit 1 Willpower, you pass. Otherwise you raise your threat. But, Gollum will not be captured (he's not in play to be captured) and you reset to 1B. Likewise for any other Escape test from the Treacheries: Even if Gollum's been lost, you still perform the test, and suffer the consequences (usually raise your threat) if you fail.

Strategy tip: If he's lost in the encounter deck, use the Impassable Bogs as good location buffers. Their 12 Quest Points will allow you time to cycle through the encounter deck before completing stage 2.