For me Tolkien in the king of prep. The reason I say this is look at the back log of notes he had for writing four books. He basically knew ever direction the stories could go in. He didn't even need that much information considering his characters were his own and unlikely to turn an unexpected direction. But you are always left like he had the legends and songs of each region all thought out. This is my goal as a Game Master. I want to have a firm grasp of the possible places the party can go.
For me the easiest process is to look at the campaign and what I best understand of it. The campaign goes right there! The location of your best understanding where it all happens best. This will allow you to throw out character that feel integrated and well positioned. It should give you a solid footing for improvisation as well. If you understand the building style and plumping you are going to be able to hand impromptu wackiness much better. But you should also realize you are not stuck to a place you know, you just need to make sure you put in similar work on new locations.
One of the ideas I noticed in Never Unprepared that stuck me as important was the thought of your notes as a database. I think that is a good idea, and wouldn't mind having an actual database set up with my notes. I may have to work on that for my own game. But I think a way to quickly incorporate it now is to make a few lists of character names, in names and far off locations. You don't even need to do anything else with them than come up with a name. Just use the names from the list and cross them off as you do. After using the name you should transition them into your post game notes with regard to how you used them. Say the Falling Coin is on the banks of the Nyr Dyv and Horatio Smeeg is a troll air pirate. The names are potential on the list and actualized in post game notes. Those post game notes are important as it allows the part to return to a game element which creates immersion.
The sort of notes you need are really dependent on your players. If they are going to kill and ignore all role playing then you need stats. If they are going to avoid every fight then you need ideas on motivations. A good example of a character motivation guide was the old GDW card suits. This gave a general idea of motivation be it cash, power, loyalty or what not. This is a decent bit of information but perhaps noting goals how they may interact with characters to accomplish them is a more useful. Its important here that combat not be ruled out. You should have an idea of how far NPC's will go to reach goals and some will be willing to risk their lives. The combat information that Paizo puts into their NPC's is very good noting when they may break ranks and how they will use abilities in combat.
One thing I have personally considered was using a sort of Myers Briggs type scale for my NPC's. Some being introverted and wanting to be left alone and others being more than happy to start conversations with the party. I don't think you will need a full four axis break down on characters but a few of the key aspects is important. For instance if a character is a quiet thinker IxTx is important. It may not be as important to know if they are feeling and judging if they are not strong personality traits. With this you can also give general traits to areas. The country may be more introverted and insular than the city. Some areas may value intuitive thought more than feeling will others very passionate.
I think the best thing I have read in the book is going with what works for you. I can't stress that enough do what feels right to you as a GM.