When people find out I work in computer security they usually, at some point, ask me about how I come up with "secure passwords". My advice (which follows) is incredibly simple - and usually gets scoffed at. "You can't be serious" etc. And yet all the crazy ways they come up with to solve the "problem" of passwords boggle me. So here, for the benefit of anyone who wants to ask me again "how do I make a secure password", is my advice :)
The first thing we need to do is consider what we need to protect against when choosing a password. Too many people lose sight of the actual dangers associated with passwords when desiging or choosing them. This is the low down on where your password could go astray:
The website you use has it's Database Stolen. Luckily it hashed passwords. Unluckily they were just sha1'd without a salt. Argh!
This is the easiest problem to mitigate. Use a complex password. People will argue for hours on the best way to turn a short word into something more secure - but why you would want to do that confuses me. Just use something complex! (ultimately my whole argument comes down to this)
Believe me; if someone is able to brute force a 30 character mix of numbers, letters and special characters, even from a sha1 hash, then I want to meet them (and give them a very expensive job). I am fairly confident that I have seen the most advanced hybrid password breaking cluster; it can handle a lot less (in keyspace terms) characters at it's current maximum (currently at 20% keyspace coverage for a number, which I can't disclose, between 10 and20 characters). Pushing to 30 characters is a huge order of magnitude (and not high on the agenda as it happens).
The point is this: provided your password is reasonably complex in the form it is sent to the server you have nothing to fear from stolen databases.
Except that they didnt even hash the password in the said database- it was stored Clear Text. No amount of complexity is going to delay an attacker in this case. Argh! (again)
Not a problem; make sure you use different passwords for different sites (admittedly the one site is compromised - but it was pretty fucked anyway).
The way people try to do this (use different passwords) amuses me. They invent these complex ways to build a password and then hash it (with sha1 usually). The problem with such an approach is manyfold.
Firstly using a sha1 hash as a password is a bad idea generally. It's a very recognisable hash and if your creating it from a shorter phrase+url then the brute forcer only has to insert a few more lines into their code. If the phrase+url is longer than the sha hash then you should simply be using that - because it is, uh, longer - the hash simply adds a very small factor of time into the attack.
Another problem is that your ultimately using a standardised system to generate the passwords. If someone is taking the time to figure out your system (or even employing rudimentary testing to pull out yours and similar password schemes) then you have a major security vulnerability. It comes down to the salting problem: salting is great only so long as your salt is secret and your hashing scheme is good enough to make brute forcing pointless.
The final issue is that everyone, well lots of people anyway, are using this and very similar schemes. That reduces it's effectiveness by increasing the profit from attacking the scheme (if an attacker can only get your password there is no point - but if they stand a chance of getting a few hundred, well, there is worthwhile investment)
My main point in all of this is simply that most of the password creation schemes you see pitched as creating "complex" passwords are actually false security. They add little actual complexity to the result - and indeed the only complex part is the faff you have to go through to make each one (every time you log in too :)).
No, real complexity is introduced through randomness. You not only need a random phrase and salt but a random scheme too. It has to be memorable and shouldn't be difficult for you to reproduce. But for a third party it should make no sense - they should not be able to guess how you are building passwords if, by some fluke, they retrieve one of them.
The Man in the Middle is usually the other big concern for techy types. Ultimately there isn't a lot that can be done to a password to make it secure from this attack. Clearly using different passwords again mitigates the damage but ultimately Prof. Mooney of Harry Potter fame puts it best:
Constant Vigilience!
With that said you can do some useful things. If your password doesnt look like a password then it may fool simple MITM attackers/programs. This is also a good mitigator for Malware attacks - which usually monitor key sequences to watch for your password.
Concern about these last two attacks (in terms of password complexity) is a fallacy anyway. You can take steps to mitigate their effect or reduce the chances of working - but if they have compromised either your system or the route to your website to that extent there is not a lot a good password will ultimately do to protect you.
What else do we need?
Lots of keyspace for one. So you need to be using numbers and, ideally, spaces/special characters. The special characters particularly will make things tough for attackers. There is no need to learn leet speak (replacing letters with numbers in words) to do this. Simple phrases which include a mathematical formula are perfectly sufficient.
Oh and make up some words - that has dual benefit of removing dictionary based attack methods and making the password more memorable to you.
Memorable is important. One reason people use the identical small phrase over and over for their password is because retaining a long password list (database even as you have to key it based on site) is time consuming. The way to do this is learn to associate the password to the site (see below for more on this) so it becomes no longer a list of passwords but a phrase you have to use when entering a site.
So what kind of magic passwords should you be using? As you can clearly see Im working up to suggesting you come up with a phrase. The caveat is it can't be a common phrase (the number of times I see "one flew over the cuckoos nest" as a password is hilarious 
) or indeed anything that makes too much sense.
Here are some suggestion:
"90% of facebookers love to log in securely"
"if 1 = 2 then twitter will failwhale again"
As you can see I am suggesting theming the password to each site to help make it even more memorable. Indeed you could even risk writing these passwords down somewhere (perhaps hidden in other prose) because their "non paswordness" means the chances of them being recognised as such is relatively low (in such a case avoid outright nonsense - it's suspicious)
Beyond that; just dont worry too much. Oh, and...
Constant Vigilance