In practice though, recognition is what matters, and it's a long and complicated process to get recognised. This instructable will take you through the steps involved, from acquiring a territory to resigning from your presidency! (Yes, that is a necessary step if you want the country to outlive you.)
Step 1: Acquire a Territory
Ideally you'd use an uncharted island, so you're not stealing land from another government. Unfortunately, these don't exist nowadays, and as soon as one is created it's claimed by a larger country.
So we're gonna have to steal from a government, why not go the whole hog and steal the land outright? Adverse posession, or "squatters' rights" is another way to get the land but, aside from the irony of the government authorising your ownership of the land just for you to take it from them later, there are drawbacks. Firstly it's not definite. Some countries don't allow it at all, and most that do favour the landowner. Also, it takes too long.
A compromise, then, buy the land from someone then claim the territory from the government when you publish your declaration of independence.
In any case, there are some points to consider about the land.
Many people believe an island to be the ultimate symbol of independance and as such the perfect place to start a country. This is not necessarily the case, and on the contrary, a land border would make a lot of sense, especially in the initial construction phase and, once you're recognised, for easier trade with that country.
A definite border is a must.
You'll need to protect your border, with a fence, wall, moat or something to stop illegal immigrants and invading armies. This is most likely the reason islands are favoured, as the shoreline acts as a firm definition and protection. A good compromise might be a peninsula, you have the land connection and the protective water surrounding.
It should be located by the sea for trade with foreign countries besides the one you were formerly part of.
It should be good farm land - you don't want to rely on foreign imports of food. I don't know much about the availability of good farm land on the coast, you might need to compromise here too.
It doesn't have to cost very much - as long as it's big enough to hold at least one person it'll do. On the other hand, as I already mentioined, it should be decent quality for agriculture and, as we'll see in the next step, large enough to fit a respectable population. The Vatican City, incidentally, is the world's smallest country at about 110 acres.
Step 2: Establish a Population
First, how do we define "permanent population"? Does that mean there has to be at least one person there at any time? Or that the head-of-state has to be there except on trips related to foreign relations? Or just that there have to be people in usual residence in the place? To be honest, I'm not sure. If I come across more information, I'll update this. Probably best to comply with all of these until you figure out which is the right one. Anyway, lets look at who we want in the country.
A farmer - so we can grow our own food and not have to rely on foeign imports.
A builder - to build roads, houses and businesses.
A doctor or someone with medical training - again, so we don't have to rely on foreign aid to tend to our sick.
A President (assuming it's a democracy). You could appoint yourself leader in the initial stages, with a view to forming a democratic system after you get recognised. Or you could call yourself king, it's up to you. Just don't go overboard with your power-trip, that's one sure way not to get recognition.
That should be fair enough as a minimum to start with. Later you'd need as many people as you can fit, but remember the smallest recognised country has only about 900 people (the Vatican City, as mentioned in step 1).
Step 3: Begin Running the Community LIKE a Country (but Don't Call It That Yet)
You might want to set up a military; I would. If you're doing this, you'll need someone who's proficient with firearms and also unarmed combat to train them. You'll also need a sailor to train your navy. You may also want a minister for defence, but you could just appoint the army's leader to this position or you could treat him and the navy's leader as equals in this role. It's entirely up to you.
You'll also want a police service for when citizens deviate from the agreed rules (constitutioin) or applied rules (acts / law). You'll also need somewhere to put them, so you'll need to build a prison and staff it with guards (or police officers).
You'll have to build an infrastructure. An airport (with an airstrip and helipad), ferry port, roads, houses, a town center. Hospital, school, government buildings. These are some things you're responsible for starting. You'll also want to attract businesses like shops and pubs. In the early stages, you're best off sticking to the laws of the host-country for the most part. That'll stop you attracting unwanted attention. Once you've declared your independence you can apply all your own laws.
Step 4: Declare Your Independence
That should be enough to get your point accross, but most of them are longer. You can include justifications for your independence, principles upon which the nation is founded, anything along those lines. Have a look at some previous declarations and get some ideas.
Send a copy of your decleration to the department of foreign affairs in as many countries as possible, particularly your neighbouring countries. Send a copy in their primary official language, aswell as yours. Assure them that you're a friendly nation, express your wish to set up trade links etc. Publish this in the national press of those countries and in your own national newspaper (you should have set this up in the infrastructure step). Retain any correspondence as evidence of their acknowledgement of your existence. This is the begining of diplomatic relations that you'll have to maintain forever if you're to get (and stay) recognised.
Step 5: Start Using the S-word, the C-word or Even the N-word (But Not the F-word!)
Step 6: Apply to Join the UN
In practice though, you'd want to be pretty well established before they'll even consider you. Try applying for Observer Status first, like the EU and the Sovereign Order of Malta. It's easier to get and will help you look more legit to other countries. if they fall for it, paridoxically, their recognition might help you get full membership.
Also join the Universal Postal Union and International Telecommunication Union, unless you want to be going abroad to make telephone calls and post a letter.
Step 7: Join a Trade Bloc (optional)
But if you managed to start your own country, why not go further and start your own union? Get in contact with the leaders of other micronations, filter out the messers and there you go. Offer them more legitimacy in exchange for giving up a certain amount of their independance. It can be a trade bloc (you all retain sovereign status but agree on certain policies, cheif among them a common trade agreement), or a federation (a new country where all of your countries become first-level administrative districts) or some combination of the two. Or you could allow them to become dependencies of your country. There's loads of ways to do this, whichever result you want.