The message of this XKCD entry is that it's much more secure to use phrases of plain words (without odd capitalization, substitutions, etc.) than to use a single word with some substitutions in one particular "common format". While that's true, I find the statement a bit weak. Their "strong" password has 44 bits of entropy, while their weak password has only 28, but a random password of the same length as the weak password has about 72. Their conclusion, that we've successfully trained people to use weak passwords, seems just wrong to me. The most common good password policy calls for random passwords, not a single word corrupted according to a particular formula, and those random passwords are far stronger than their phrase-based password.
While 44 bits protects against their hypothetical 1000 guesses per second, it's nothing against faster brute force attacks. I know, they said the average user shouldn't worry about those, but if a user is going to worry about brute force attacks at all, I'm not sure why they should ignore the possibility of faster ones. If we don't ignore them, their strong password could be cracked in 10 hours, or in a few seconds on a botnet, whereas the random password would take thirty years on the same botnet.
I use random passwords, and I don't find them especially hard to remember because I don't try to remember them. I let my fingers worry about that. I may not be able to recall a password at all, but my fingers still know how to type it. If the password hasn't been typed recently, then it can take a while to strike upon the right muscle memory, but I'm not sure "correct horse battery stapler" would be much easier, if you hadn't typed it in a long time.
That said, I actually do support phrase-based passwords: not random ones, but ones that are meaningful only to the user. I use some of those, but with words from multiple languages and additional numerals and symbols in an attempt to prevent word-based attacks. They can be especially easy to remember if you have a mental image to go along with it. (They may have been alluding to the use of mental images in the last panel.) But I think the real solution to brute force attacks (as well as precomputed hash databases, etc.) lies in training software developers more than users. The key is to use a hash that both includes salt and is slow (a la bcrypt). If the hash takes a couple seconds to compute, attackers will have a hard time getting high guess rates in any case.
To prevent the computation from taking up all your server time and exposing the server to DOS attacks, you can do it on the client side (with the server providing the salt after receiving the login name — it's usually not a game-breaker to treat salt as public information, especially if you incorporate a timestamp into the protocol to prevent offline attacks and replay attacks). This should strain attackers' resources, since they usually have enough network bandwidth to attack many accounts or sites simultaneously, but CPU power isn't so flexible. This protects all users, even ones who use bad passwords, because it greatly increases the cost of any brute force attack, and thereby reduces the likelihood that attackers will actually attempt one. If the application has a user interface, you can play a short animation during those couple seconds so they don't get the impression that "nothing's happening". You can even make the calculation adapt to different users' computer speeds fairly easily. If the app doesn't have a user interface — their example was a web service, but in that case people usually aren't typing passwords in manually anyway — you can use standard session techniques to only require the login to be done once.
That's my opinion on the matter, anyway. :-)