Cultural and diplomatic victories will require you to start on them early -- cultural, you need to get your cultural buildings up and running quickly so you can start accumulating culture points and get that double-culture bonus from old buildings; diplomatic, you need to cultivate a large bloc of friendly AIs, which can take time especially if you need to spread religion to do so.
Domination and conquest are basically continual om-nom-nomming of the closeness vulnerable AI. Build army, conquer, recover, repeat. Of course, the sooner you start on this, the better, but an early rush is helpful for most victories anyway.
Space race and time victories extend well from domination/conquest runs since you have a nice big empire, which means more points (for time) and more mega-production cities (for spaceship parts). Generally I end up going for space if I can't be arsed to conquer the last few AIs (e.g. they've finally caught up in tech and are isolated on a separate continent, and me without a significant navy).