Here's a few tips/tactics that have helped me along:
1. Scout early and aggressively, including with your starting warrior. This is more important on land heavy maps, of course.
2. Tradition is pretty good, especially if you have a nice capital site and a couple places to settle. Liberty is pretty good if you don't. Honor and Piety are harder.
3. Settling close to other civs means a greater chance for war.
4. Micromanage in the beginning, including the lock tiles and set city focus to production trick. You switch tiles to a food tile every time your city grows. When building settlers, lock all tiles to hills and other hammer tiles. Later in the game, micromanagement isn't so necessary, but you still want to cycle through your cities from time to time.
5. Caravans and cargo ships are important. They provide food, gold, and diplomatic bonuses. Later in the game, they can give hammers.
6. BNW punishes warmongers heavily. If you must take cities, only take them in peace deals only during the early going to avoid much of the hit. Avoid making friends with civs that you know will attack city states. When you notice a civ getting denounced, you can join in and get diplomatic bonuses. Generally, being a peacenik makes for an easier game. Diplomatic victories are the easiest kind, in my experience. I've yet to get a domination win.
7. Some of the new BNW civs are really powerful, like Poland and Shoshone. There's a couple good guides for playing them on this message board, although aimed at high difficulty levels. Incidentally, don't get bummed out if you don't do as well as the people posting guides. Nobody ever posted a guide demonstrating how they got crushed, even though I feel confident that everybody gets their ass beat from time to time, or at least used to while they learned the game.
Personally, I plan out a general strategy that I want to try in advance. For example, I used to be pretty keen on getting Desert Folklore and using all that faith to dominate the religious aspect in various ways. Lately I've been trying other faith or culture pantheons. This requires a lot of restarts, not because I'm looking for an awesome start so much as because I have a particular one in mind. Awesome starts are nice, though.
Replaying segments of the game is a good idea. Once I get the start I want, I might save it and if I don't like how things are going by the medieval period, I'll replay from the beginning to see if I can't do better. If I'm happy with how I'm going, I'll save it again so I can back up if things fall apart in the midgame. If it doesn't work out, I'll try again with the same civ and see if I can make the strategy work.
I improved a good deal at Civ IV by playing succession games. Unfortunately, Civ V doesn't seem to have a lot going on with succession games now. However, maybe some of the Warlord/Prince players reading this could get together and do a King or Emperor game. Usually you want to step up the difficulty in a succession game because strategy gets hammered out by the group and if somebody turns in a lackluster set, the next player will probably salvage it.
Link to the SG forum:
http://forums.civfanatics.com/forumdisplay.php?f=408