Let's just dive into this, shall we? This tutorial will have six main steps, but they are all pretty large. By the way, I will be using a Science Fiction theme for this tutorial. I am also sorry for using Texture Pack links, but I want a way for people to find those good Texture Packs in their maps.

Step 1: Coming up with the main Theme / Story.

A good Theme would have to be something original. That means no stealing from other maps, books, movies, TV shows, or anything else really. If you do that, eventually, someone will figure that out, and call you out. Then your reputation might just go plop. That, and it's not really that fun, using a magic school as a base or something.

What you should do: Think of a book genre you like; be it Sci-Fi, fantasy, adventure, or anything but romance. Remember to keep it child friendly! So, if you want a map where you patrol through space, do that, but remember it may be harder to make.

Step 2: Using Texture Packs.

For a good medieval style pack, I recommend John Smith, which can be found here: http://www.minecraftforum.net/topic/26727-johnsmith-texture-pack-v94-32x-125-12w25a-new-update-0622/

A good Sci-Fi pack would be the Mine Wars, which is a Star Wars based pack, which can be found here: http://www.minecraftforum.net/topic/373580-16x125-mine-wars-a-star-wars-texture-pack/

For a more magical feel, use the Dokucraft: The Saga Continues pack, with the customizer, which allows you to change some block textures. It can be found here: http://www.minecraftforum.net/topic/513093-32x16x125-dokucraft-the-saga-continues/

If you need a different block, or think it won't look good, consider making your own TP. Do not, I repeat, DO NOT edit somebody else's textures.