This is the game's main subquest (or perhaps main quest?), meaning you have to start from the beginning and perform various tasks along the way. I'll break down what you need to do by area. Since this is kind of long, I'll start off by a quick listing of what you need to do and then follow with longer descriptions for each area.
Mines: Pick up the Udjat Eye by combining key and chest.
Jungle: Use the Eye to find the hidden exit to the Black Market.
Black Market: Buy or steal the Ankh.
Ice Caves: Use the Ankh close to the Moai head to get the Hedjet.
Temple: Kill Anubis to get the Scepter, and use it with the Hedjet to open the door.
You need to collect the Udjat Eye, which is done by bringing the key to the locked chest (or vice versa). These items can spawn in any of the four Mines levels, but they're always in the same level, so if you find the key and reach the exit without finding the chest (or vice versa), you've missed it and should start over. This is pretty simple - just keep an eye out for both items and you should easily be able to collect the Eye in every run you make.
One thing to note is that it seems to me that the rolling boulder trap that's activated by stealing the golden idol can destroy the key (but not the chest), so avoid triggering the trap if you think the items are on that level.
Here, you need to use the Udjat Eye to find the Black Market, which is a hidden exit somewhere in the walls. Unlike the items in the Mines, this is not as easy to achieve every time you play, since the entrance may be dug deep into a wall or even the ceiling, meaning that if you don't have a lot of bombs or sticky bombs, you won't reach it. The exit is always dug into some kind of wall, though, so you need to try to get here with at least 5 bombs.
What happens is that the Eye icon in your HUD starts blinking and making sounds - it's pretty unmissable - whenever you're close to the exit. If you're one block away, the Eye goes crazy and blinks rapidly.
Note that you *can* see the exit without the Eye sometimes, due to the leafy bushes surrounding the exit (you can see them sticking out behind a wall sometimes), but that there are reports on the net that you cannot complete the City of Gold quest by finding the exit without using the Eye.
Finally, after finding the exit, you need to bring $50,000 or some shopkeeper-killing skills into the Black Market. You need to purchase or steal the Ankh (which is located along the rightmost wall), and there are a lot of shopkeepers in here so buying it is the safest bet. If you're only a few thousand short when you find the exit, you can enter and probably find the missing money lying around the Black Market or play the spinning wheel game to earn more.
Make sure to not die while carrying the Ankh! It's an extra life but you need to die with it equipped at a certain point in...
This one is simpler than the previous two. All you need to do is keep the Ankh intact and progress through the levels until you find the big moai head (easter island statue). It's large and fairly unmissable as long as you don't speed through the levels.
You can die anywhere on the level, in any way, once you find the moai head, so just jumping on a spike trap or down into the abyss will work. Also, while you keep anything permanently equipped as you get resurrected (jetpack, shoes, compass, etc), you lose anything you were carrying in your hands (probably a shotgun or mattock).
Once resurrected by the Ankh in proximity to the moai head, you'll be teleported inside it and automatically pick up the Hedjet helmet. Inside is an exit that takes you to the next stage.
In the Temple, you need to find and kill Anubis (the egyptian god-type enemy) to get the Scepter. He's tricky to kill but the two best methods are a weapon (shotgun, plasma cannon, freeze ray) or sticky bombs - he'll take three hits of each. Once he's dead and you've picked up the Scepter he drops, proceed to finding the golden exit door which will open when you're carrying all the required items. When you do this, you lose the Scepter and will be without a weapon, and in my experience, Anubis and the exit seem to always be on different levels.