I was introduced to Settlers of Catan just a few weeks ago here. I plan on buying it and I would like recommendations as to which expansions I should get.
The two biggest expansions for Catan are Seafarers of Catan and Catan: Cities and Knights. I previously asked the question, "How is gameplay improved in the Cities & Knights Expansion?" recently before buying it myself. I would check out the answers there for some other opinions on that expansion. There is also a third expansion, Catan: Traders & Barbarians, but that isn't as popular.
Seafarers of Catan
This was the first expansion for Catan. The expansion expands the size of the board and gives you the ability to have islands separate from Catan. The game comes with a number of different scenarios and the ability to create maps with random landmasses. (Random maps on Seafarers is a favorite of one of the people I play with, and how we usually play.) Besides adding boats which are roads going across the water, and a pirate to act as a robber, Seafarers doesn't significantly increase the game.
Catan: Cities & Knights
Cities & Knights was the second expansion for Catan and take the base game and builds up on it. Three commodities are introduced to the game: Coin, Paper, and Cloth. Cities, now instead of producing two resources, produce a resource and a commodity for ore, wood, and sheep. The development cards are not used and progress cards in three colors are now used. Progress cards are gained by developing your cities, and can't be bought. You use the commodities to upgrade your cities through different levels to increase the speed of you earning progress cards.
Knights also move from being cards to being tokens on the board. In addition, every so many turns, the barbarians come and attack Catan. All active knights defend, and if Catan wins, the person who helped to defend the most gets a victory point. If Catan looses, the person who helped the least, looses a city. A third event dice determines when the barbarian moves or when progress cards can be generated.
All of this increases the length of the game and makes Cities & Knights plays slower. It's a much more strategic game with Cities & Knights. The progress cards also give you a lot of different options. A number of cards directly harm other players, while benefiting you.
Catan: Traders & Barbarians
This is the one I haven't played, but I do know it adds a lot of different scenarios and variants to Catan you can play with. It includes the Catan Event Cards, and Settlers of Catan: The Great River. (As a side note, I know my local game store carries The Great River as a separate expansion.) The wikipedia article on this expansion has a lot of information available about it.
5-6 player Extensions
The main game and each expansion, has a 5-6 player extension for it that lets you play 5-6 players. I have extensions so I can play the main game or Seafarers but have never actually had 5-6 people to play it. Friends of mine speak very highly of playing Catan with more people though. Adding more people does slow the game down though and if you play Cities & Knights with 6 people, your looking at a very, very long game.
I love variety when playing games, and I find Seafarers adds a lot of variety that makes each game different. You get this with playing random maps with the core game, but random landforms really diversifies what's going on. We've had games with large landmasses or narrow landmasses. If you want to break out of the standard Catan island, this is the expansion for you. I can also speak highly of Cities & Knights. It's a different type of game, but adds a lot of depth and if your looking for that, get it. No one has recommended Traders & Barbarians to me yet, so I would say the jury is out on that one for me. I would suggest both the other two expansions first, and get Traders & Barbarians if your still looking for more Catan.
Finally, I would get the 5-6 player extensions on as need basis. If you at least get the core game extension, you can at least play Catan if you have more people then usual.
Seafarers adds ships to the game, which you can use to explore separate islands; they are like roads, but go over the sea. The addition of ships adds some balance that was missing in the original game; since ships cost wool and lumber (or sheep and wood, depending on the terminology you use), they increase the value of wool, which in the original game is frequently less useful. Apparently, ships were originally supposed to be part of the base game, but were removed to simplify it; but I find that adding them back in adds balance back to the game.
Seafarers also increases the sense of exploration in the game. In the original game, you're just settling one island that you can see all of to start with. In Seafarers, you are exploring and settling new islands; in some cases, you don't even see what's there until you get to them. Seafarers comes with several different scenarios with slightly different rules and different map layouts; in some you have many small islands, while in others you have one large island like the original, with a few small satellite islands.
I find the other expansions I've tried less essential. Cities and Knights can be fun, but it focuses on city development and knights which protect you from barbarian attack, instead of adding more to explore and balancing the basic game. I've never tried Traders and Barbarians; I believe that it is a collection of several small expansions, that you can mix and match, or mix and match with Cities and Knights or Seafarers. The 5 & 6 player expansions can be good if you wind up with more players than basic Settlers can support, but I find that they make the game take longer without making it much more interesting, so I think that 4 player Settlers or Seafarers works better.
This is a small expansion that I got in the now-defunct Games Quarterly magazine (according to BGG, it was in Issue 12 of Spring 2007).
Basically, there are fishing segments on the shoreline, and if you have a settlement touching one of these fishing areas when the number is rolled, you get a random fish tile. You can trade in fish for various favors, such as moving the robber back to the desert, getting a free resource, a development card, etc.
It was apparently included in the Traders & Barbarians boxed set, although if you only want this expansion, you'll most likely have to look on eBay to get it.
The way I usually tell it to people is this: what do you like about Catan, and what would like to improve on? Because each expansion generally tweaks one broad area.
Seafarers is ideal if you think Catan is fine, but wish it was bigger. More space to place things, more exploration, and generally just more Catan. Same basic rules, new maps.
Cities and Knights is best if you think Catan is too simple, or too easy, or something like that. It makes the game deeper instead of broader, and adds more strategy options.
Traders and Barbarians is actually my recommended expansion in general, because it is very diverse. It's good if you just want to tweak the game a little (I never play without Harbourmaster now, and I often bring in Fishers). It's also great if you want something different: from a minigame that's like Cities and Knights light to a modification that basically turns Catan into an entirely different game.
I think, for the money, T&B really just gives you the most stuff. Seafarers I recommend second, unless as I said, you just want bigger Catan. C&K I recommend last, unless the group just really wants a more complex game, and even then T&B probably covers that.
The 5-6 Player expansions I consider obvious: if you often have 5 or 6 people who want in on Catan, you need the expansions. You could also get the 5-6 basic game expansions as a kind of mini-seafarers, if you just wanted to play with four people a little less aggressively with a bigger island.
I think Cities & Knights is my preferred expansion out of that and Seafarers. I'm hoping to get Traders and Barbarians soon.
Seafarers I feel didn't add much to the game, it's easy to pick up, but honestly most games are won by simply staying putt and not using ships/visiting islands which is what seafarers is all about.
Cities & Knights adds a whole new dynamic to the game, and you have to completely re-shift your strategies. The problem with it however, is once you pull into the lead it can be quite difficult for those dropping behind to make much impact in the game.
It should be mentioned that the base game and Seafarers feel more like Monopoly (a family-friendly game of building and trading), while Cities and Knights feels more like Risk (even deeper strategy, and very cut-throat).
I would not call Cities and Knights family-friendly at all - you get a lot of cards, and every other card (it feels like) is a "screw-someone-else-over" card.
For someone who has just started playing SoC, I would recommend Traders and Barbarians since the rule extensions are fairly minimal. C&K rules greatly complicate the game so I would recommend that once one is more familiar with basic game play. In both cases and with Seafarers, the rule extensions are enough to make strategy different.