The post above pretty high-level, focused on the overall process and timeframe rather than the detail. There's sections in there labelled "detailed planning" and "writing the characters". What do you actually do there? Here's some more detail.
Concept: What's your game about? What's the elevator pitch? This should give you an immediate idea of the sorts of people who will be there and the sorts of things they will probably be doing - which in turn gives you your initial ideas for characters and plots.
So for example if you're thinking about a pirate larp, then that immediately suggests characters like pirate captains, a runaway governor's daughter/son, maybe a bold hero in disguise, and plots such as finding the buried treasure, breaking the curse of the Black Spot, deciding who to attack, or electing a new Pirate King.
Your concept needs to give everyone a reason to be there and a reason to stay and interact (at least initially).
Classic concepts include parties, funerals, political meetings (e.g. peace summit, election of a new leader), crises or investigations. Some games do use a "slice of life" approach. either to explore it, or as an introduction to a crisis or Things Getting Weird.
You may want to explicitly think about themes, or just let them emerge naturally as you write the characters.
Outline: Now you've got your concept, get a big bit of paper or a google doc, and write down the ideas for characters and plots it immediately suggests. Any fiction or historical sources you're using as inspiration? Write down the ideas from those too. Then write down anything else that comes to mind that seems like it could fit.
It helps if you have someone to bounce ideas off during this stage. But the aim is to throw ideas at the wall and see what sticks. Ideally, you'll have more ideas than you actually end up using, which is good - you'll have redundancy for when ideas and character concepts inevitably don't work out. Or for your next game.
Steal shamelessly. Both in terms of the plots that naturally belong in your concept, and those that don't. I've seen Western games with characters based on Lancelot, Guinevere and Achilles, while Hamlet seems to crop up everywhere. Some plot tropes are eternal and are re-used over and over again.
You can do this upfront as part of a detailed planning phase, or while writing. Either way you're going to have to think about the same stuff.
Characters: The first things you should ask about a character is who are they? Why are they here? And what do they want?
Goals: This is a whole topic in itself, which Jan-Yves has covered quite well in Away from goals in LARP. But the short version is: characters need something to do during the game (or at least when the game starts). The easiest way to provide that is to make them want something, to give them goals. I'll quote Jan-Yves here:
While they can be pretty flexible, they often fit one of a few basic templates (examples include: “Get another character to do something”, “Find out something about another character”, and “Get a thing off another character”). Good goals are generally active (that is, to achieve them you need to do something) and outward-facing (they make you interact with someone else). Obviously, if you put twenty people in a room with active, outward-facing goals, what you get is interaction, which drives play, which makes the LARP go round.
There are other ways of doing it, and that article has some good ideas about easy goals and participation goals. And its fine to have some goals which are inward focused e.g. "decide what to do about X", provided there's enough outward-focused stuff to push interaction.
Its an unwritten rule that if you give a character a goal, there must be a solution somewhere in the game (though it may not be easy to find, and it may not be exact or easy). That said, people often want things they can never credibly achieve, and that can provide powerful character motivation even though their struggle is unsuccessful. Just be careful about overdoing it and creating player frustration - unless the aim of the game is to explore the frustration of failing to achieve the unachieveable.
Whether you list the goals explicitly on the character sheet, or have them implicitly in the character's backstory is a matter of stylistic preference.
Relationships: The other big driver of a larp, and again a whole topic in itself. Most larps are set in social situations where the characters know at least some of the other participants, so its important to think about what they think of one another. Relationships help shape the landscape of the larp: goals tell characters what they want; relationships help them achieve them (and rope them into other things).
No matter what, every character should have at least one friend or ally, someone they can interact with. The Bad-Arse Loner is a popular trope, but characters with no friends and no reason to talk to people are no fun to play.
Romantic or proto-romantic relationships are a staple - generally players love the soap opera. Just be aware that some players do not like them, that playing that sort of relationship requires trust, and that there are players who can't work with other players. But those are problems for the casting quiz.
There are games where the characters don't know one another
Information: Most theatre-style larps involve secrets and uncovering hidden narrative (hence the name "secrets and powers" games). Characters will usually have secrets, usually want to find stuff out, and usually know stuff which other people want to know or don't want them to know.
Think about who knows what, and the likely flow of information around the game in light of the relationship web. Characters who hate one another probably won't share information while friends will. You can use this to make things easier or harder to find out. If information is critical, have it in multiple places or have multiple pathways to it if you can (its not always credible, but...). Try and avoid single sources, especially those with reason to lie to people trying to find stuff out. A single source is a single point of plot failure.
Don't rely on inconsistencies as a sign of deceit or that something weird is going on. Players in-game do a lot of work to make the fiction consistent and seek coherence from the incomplete information on their character sheets. Unless backed by multiple sources, inconsistencies are likely to be seen as an inevitable mistake by the writers, rather than a plot signal.
Don't have "keep your secret" as a goal, since it is inward facing and does not lead to interaction. Instead, have secrets be known to other parties, and use them to drive plots around blackmail (and getting out from under it), or confiding in someone and getting advice, or managing or spinning or coming to terms with the revelation, or dealing with the consequences.
Character sheets: There are lots of different ways of writing a character sheet. I approach it as an exercise in technical writing. The purpose of the character sheet is to convey information to the player, and so help drive the game. So I focus on brevity and clarity. I usually start with a little about who the character is and why they're there, and move from that into the plot dump. Sometimes, if a character has a defining goal or relationship ("You've always wanted to Rule The World...") I start with that instead. Plots usually go in order of importance and involvement. I finish up with mechanical stuff, lists of goals, and a summary of relationships (which usually mirrors the stuff earlier in the sheet).
Often you can crib one character's description of a plot for another (with changed names etc). This helps both the writing process and also with consistency. Inconsistency is the bane of larps, and you don't want players having conversations in-game like "So, remember the bank robbery we were involved in?" "What bank robbery? [OOC] That's not on my sheet".
Character sheets should ideally be short. Many people use two sides of A4 in a reasonable font size as a target. You can go longer (I've seen sheets as long as 20 pages), but the cost is likely to be players having to refer more frequently to the sheet during play.
I find that putting names of other characters in bold in the text helps highlight salient information.
You write the game, then you run it, right? Not so fast. There's another important step:
Consistency-checking: It is vital that your game gets at least one editing pass both to tidy the language and (more importantly) consistency check it. We've all had games where inconsistencies have popped up, often embarrassingly: "best friends" who don't know one another, multiple people who saw X do something and its not mentioned on X's sheet etc. So, you need to try and minimise this.
Go through all the character sheets and check everything. Where a character mentions a particular relationship or series of events, check all the other characters involved to ensure that they have the same picture (or at least, a plausible own version thereof - because perspectives differ and relationships are not symmetrical). Also make sure that all key information is present: if the right to the throne of Kingdomia is conveyed by finding the Jeweled McGuffin, then every non-clueless claimant (and anyone who might adjudicate) needs to know this.
You will inevitably miss something. But a good consistency check will help make sure its only one thing. And your game will be better for it.