I think that DaveMcW's advice is good. The problem with the game is that there are so many ways to victory that it seems overwhelming. Play a lot, there is nothing like experience.
Also take San Pelligrino's advice and read as much from the War Academy as you can. The Academy is on the Main Page in the left side bar.
One thing that most new players do is try to build up their infrastructure at the expense of their military. Especially in the early game it is necessary to have a strong military. I used to build and build city improvements, with only a spearman to protect each city. I got my ass kicked. Now I spend a lot more time building my military and sending out settlers as fast as possible. I find that if you have a strong military you may be behind in score at first but then you start catching up and eventually pull ahead.
So go for Horseman and Swordsman, instead of the techs in the middle of the tree. Search for horses and iron deposits and build cities so that they are within your city radius. Then build a road to connect them. Pump out those Horsemen and Swordsman and the world will give you the respect you deserve. When you fight and win your units will become elite. Then use those units in fights where you know you will win and hope to get a Great Leader (1 chance in 16). Getting Great Leaders is one of the keys to the early game because, you can use them to build the Forbidden Palace and Great Wonders.
Having a strong military also enables you to take the enemy cities and then negotiate for peace from a position of strength. Never agree to a peace treaty without getting something from them, usually their techs.
Along the way you can build your infrastructure, but don't concentrate exclusively on it at the beginning.
Here is a recent post from Moonsinger that has another good starting strategy:
"Regent, Monarch, Emperor, or Deity, the starting method is really the same for all levels.
1. Start your first city at 4000BC and tell it to build 2 warriors. If you don't have Pottery, research it now and set your science slider to 100%. You will discover Pottery within 22 turns or less (22 turns at Deity level, much less at lower level).
2. After building the first 2 warriors, set it to build a great wonder, barracks, temple, or whatever that takes the longest time to build. Note: we just want to store the shields at this point. Once we discover Pottery, we will immediately switch it to build a granary. In the mean time, road and irrigate the food bonus tiles within the city. After the granary is built, set it to continuously produce settlers. That's it. We now have a settler production structure in place.
3. Find a good spot to build your second city (make sure it get good shield production and not too far from your palace) and immediately build a barracks. After the barracks is done, set this cities to continuously produce military units. That's it. We now have a war production structure in place.
4. Depend on your playing style, do what you will with the rest of your cities. You could build more settler production city or more military production city or even great wonders (culture production city)."
