The Diplomacy Screen is your friend. Use it. Make friends quickly, you won't last long alone against other empires who are allied. Trade and alliance both give you 10% of your partner's resources (minerals, fuel, and ag) so there is an added bonus for joining forces. This, of course, only applies in alliance games. If you're in a blood then find everyone else and then nuke 'em till they glow.
The question of proper use of diplomacy is one of the more hotly debated aspects of SC ettiquette. You do want to get the trade bonuses from partners and allies, but you don't want to step over the lines and ruin the game for everyone. Use diplomacy to its limit, but if you do then don't be surprised if the others have the same idea and are using you for their own convenience. Unless you know everyone involved (and even then in many cases) you should keep in mind the words of one crafty veteran — "diplomacy is the art of saying 'nice doggie' while you look for a bigger stick."
So how do you select an ally? One approach is to simply ally with the first person you find. This can work well in that it gives you a turn or two head start on that trade bonus. Some people, though, prefer to ally with people they know. Both approaches have the potential to set up uneven teams where some players get left without an ally, so use of the diplomacy screen helps to get everything sorted out fairly for everone.
Note that simply allying with a player who has a lot of wins on his record is no guarantee that you will get a good ally. Stats mean nothing. Let me repeat that, STATS MEAN NOTHING There are too many players who still inflate their stats through use of nuke babies, get into lots of grudge matches against newbies, and do all sorts of things to pad their record. Some do it because they want to claim to be as good as their record indicates, some do it to make less experienced players more likely to ally than fight. Respect these people, but be willing to stand up to them. If their stats are honest then they'll teach you something as they nuke you; if they aren't, then like most bullies they will typically back down.
Diplomacy is more than just the actual truce-trade-alliance settings. The real, and lost, art of diplomacy is its use in simply talking with other players. The most obvious way of doing this is communication and coordination with your allies. A team that coordinates their moves, shares information on the enemy, etc. will last much longer than a team where each member acts independently.
Talking to the other players will help you out not only in the current game, but down the road as well. It lets you get to know the other empires — the ones you will be meeting over and over again — and form an opinion of how to approach them in future games. It can also be used to learn from other players. The true masters of the game are typically happy to share their experience with new players, but they won't know to do so unless you ask.
Not all communication, of course, has to be friendly and innocent. A rather obvious trick is to send a message to your enemy, ("we're attacking *next* turn, right?") pretending to be talking with your ally. While such stunts rarely work, they can at least make the enemy player start to hesitate as they decide whether the message was genuine or not. Even the creative use of Broadcasts rather than private messages can be just as effective with the proper wording.
Not part of the Diplomacy Screen, but just effective (and sometimes more fun) can be the use of ship and/or planet names to get your message across. This is an old trick for opening a private communication channel in blood games. Other things to try - change your icon to that of an enemy empire to confuse him as he looks at the map, in games where you can use a custom icon use the same icon as an uncolonized planet, name your planets where there are enemy ships to one of his planet's names, name your ships " , , , , ," to make it appear in the update message that you have more than you really do. Most of these are really toys, fun pranks to play but unlikely to phase a veteran player. Although, in the days of yore before HTML was removed from the broadcast (and when we played on 2400 baud modems) one crafty player did manage to fend off a nuke by sending a 400K image of Godzilla to his enemy. Hey, nobody said you can't have fun while you nuke 'em out...