I'm no expert on early war, but I can offer a bit of advice from what I've seen so far, including my recent and highly successful BC-era annexation of Russia by Egypt on Prince (it would help to know what diff you're playing, too). In all of this, I assume "early war" to mean pre-catapult wars, probably also before you have all the techs and resources to mount a "real" combined-arms offensive.
1) You need a reason - a good reason - for early war. It's dangerous, expensive, and highly random. Unless I have some compelling reason and/or circumstances, I would develop my cities and wait for catapults. Even a good UU, by itself, is not enough IMO, though it may play into things. In my Egypt game, my first three cities blocked off the north end of the continent (providing space for 3 solid cities later on). Cathy's second city had just nabbed the copper in the spot I had intended for my third city, but it was a looong extension for her from her capital (something like 8 tiles horizontally). My immediate neighbor to the south was Tokugawa, but he would be struggling with a jungle and thus be slowed down for a while. I was in second place point-wise behind Cathy. She had founded two religions in Moscow and Toku and Capac (a ways off to my SW) had converted to them already. So there were many reasons for a solid early war here: a) resources - I needed the copper, b) geography - I had a narrow, clearly defined front with Cathy and her copper city was too far from the capital to be protected well, c) UU - I had War Chariots, she didn't have an ancient UU, d) power - she was the current leader, e) money - Moscow was a double holy city. Had any of those not been true (especially b), I probably would have held off and built up.
2) Time is of the essence. If you attack before catapults, you're going with brute force attacks, often at even odds (at best). Letting the AI build a single extra defender may require several extra attackers on your end. Similarly, resource hookups are just coming online at this era, so don't wait to assemble an entire army and don't try to get every military tech you'd like - send troops out to pillage improvements, harass enemy workers, and gather intel. After taking St. Petersburg with my war chariots, I was going to camp for a few turns to wait on two more chariots that were completing. Then I thought better of that and sent them off. That decision was quite fortunate for me, since they spied a mined plains tile when they reached Moscow - iron (which I couldn't see yet). Had I waited a couple more turns she would have had spearmen and my Chariot offensive would've been toast.
3) (Corollary to #2) Mobility is key. If you have flat terrain, use horses to get your troops out to the front lines quickly. Regardless of terrain, use workers to build roads to your enemy's doorstep, preferably before you even declare. Forget about other improvements apart from resource hookups - get your roads built.
4) You need total dedication. You don't have much to work with, so every city needs to turn wholly to military production. Forget about growth, forget about infrastructure. Every city needs to build units at the maximum speed possible. There will be time enough to grow and develop after you've decisively eliminated your enemy.
