I've found 1Password (http://agilewebsolutions.com/products/1Password) to be a great solution to this. It automatically generates passwords for you and saves logins on an encrypted file. The only problem I've found with it is that when you go to use a friend's computer or a public computer you don't always know your passwords. A web service version of it would be convenient, but the security implications are obvious..
For the sake of a working solution I also just store passwords in encrypted files (using encfs, though) and stop worrying about accessing everything from my non-main computers.
Script for new passwords follows, for the fun of it. I have stuff added afterwards to save the username, website, and password to encrypted files.
#!/usr/bin/env python
import string
from random import Random
okchars = string.letters + string.digits + "!@%^_&*+-"
print ''.join( Random().sample(okchars, 40) )
