I haven't myself moved up to deity level yet. What is your chosen civ and plan?
Zulu, Arab or Aztec are generally good for an early domination rush. Germans are good for a longer term domination strat with automatic elite upgrades. England are good with early defense with their archer bonus, then late attack and defense with double naval support (yikes for a doubled battleship fleet bonus), and also good for cultural victory from early monarchy bonus.
A good forum with discussion is CivRev - Strategy & Tips - Civilization Fanatics' Forums.
There is a lot of discussion and strategy over there.
I like the Aztecs because their warriors self heal and they have attack bonus. They also generate 50% gold bonus and it's all about the benjamins yo.
I haven't even thought about playing on Deity yet Bandit, you're insane.
I just won on Deity via Domination. I could have won a Cultural victory too, but I couldn't resist nuking the final enemy capital.
I just beat the game of the week on Deity by 1300 BC