Because of the underlying themes of the campaign, I first needed to address the religions of the world.  I wanted the PCs' religion to feel familiar to the players since the characters themselves have grown up inundated in it, so I kept the pantheon of the campaign fairly familiar; before the campaign started, I wrote up a wiki page describing how it would differ from the standard D&D 3.5 pantheon, and I kept those differences small enough and logical enough that the players would be able to grasp it fairly quickly.  Once I had the PCs' religion sorted, I created a private page linked to that page to describe the religions of the other races of the world.  The PCs would uncover bits and pieces of information as the campaign progressed, so keeping my notes in a format easily dropped into the player-accessible wiki really cuts down on the work I have to do when putting together handouts and session notes later on.

(As a side note, I've found it to be very helpful to keep a wiki-like structure for the players to access and edit.  Many services exist for this type of journal, but I just created a public and a private space on wikidot; I didn't need the fine control offered by the other services, and I like wikidot's markup.

With the basic religious framework of the campaign roughed out, I moved on to think about what the players would be running into first.  I knew that they would be growing up in a tightly-knit and geographically-isolated civilization, so I began there.  I mapped out the players' homeland and began writing up notes about the culture of that civilization.  For each of these pages, I created corresponding skeletal pages on my private GM-only wiki.  As I thought of new ideas for anything, I wrote them up and refined them on the GM wiki; once relatively clean, I would then copy over what the PCs would know onto the player wiki for everyone to see.

Since this campaign has a specific them and definite planned setpieces, my next step was to write up a rough "outline" of these setpieces on the GM-only wiki.  I didn't try to outline an entire story, only the major setpieces.  I know some are likely to occur later than others, but I didn't organize them beyond that; I still want the players to drive the actual story arc.  It is likely that some of these setpieces and story moments will never be hit, but I still keep notes on them on the GM wiki to inform the theme and atmosphere of the campaign in total.

Now that I had the basic campaign structure laid out, I started work on the true task of "alienating" the players.  I created notes on the outside world on the GM wiki and began building up a bestiary of creatures and races.  Each is based on a standard D&D creature type or race, but all have been tweaked to make them less immediately identifiable to the experienced players.  I started by tweaking the appearance of each -- of course, as this will be the first thing the players have to respond to when first encountering these creatures.

For antagonist creatures, I mixed and matched various abilities to re-work the feel of the creatures, trying to keep the signature abilities of a given creature type.  My goal is to make each type of creature clearly identifiable as being that type of creature... but hopefully only after you've seen everything they can do.  For example, I reworked the appearance, behavior, and abilities of trolls significantly, but I kept their signature regenerative powers and weakness against fire.  Once the PCs had faced the trolls a few times, it became apparent that they were trolls, but for those first few encounters, the PCs were as taken aback by the unusual creatures as a real person thrown into that situation would be.

For intelligent creatures not designed to purely be antagonists, I had to do more work.  I took the cultures specified in the normal books and started with those; then, for each major race that will play a role in the game, I mixed in traits from various real-world cultures to try to slightly twist the experience the PCs would have with members of that race.  In that way, I wanted to allow the PCs to slowly become comfortable and then be thrown by a cultural norm of the race multiple times, hopefully mirroring the experiences of a foreigner thrown completely unprepared into an alien world.

By this point, I had been doing prep work on the campaign for something like 3 months.  This is normally much more time than I would spend preparing for a campaign, but I expected this campaign would require more up-front work due to the additional customization I wanted to do in the campaign.  Now 3 months into the campaign, I think the up-front work I put into flavoring the magic, religion, and creatures of this world has really helped keep the players involved in their characters' journeys.  They've been in the world exploring this unfamiliar territory for months of game time, but they are still relatively lost and alone; they're very alien to others, and everyone else is very alien to them.  I think this has kept the players engaged in the discovery aspects of the campaign, though.  Every session, I see more and more questions and more and more poking into the corners of the world to try to figure out just what is going on and how to interact with everyone.