Right off the bat you have the option of choosing from Charmander, Squirtle and Bulbasaur. Neither of them have a main advantage over the others. You will eventually encounter the other 2 Pokemon you don't pick over time so it's not a critical decision (the one you picked will also show up a few times along your journey and at a higher level).
One thing to note is that you can also get Pikachu as a starter Pokemon. To do this its a bit more tricky, first ignore Charmander, Squirtle, and Bulbasaur and walk away from your area. They will re-appear in your new area, you need to repeat this and have them disappear and re-appear 4 times before Pikachu appears with them. From here just click on that little yellow Pokemon and throw a ball at him to make him yours.
From your normal map view select the bottom right corner to see Pokemon that are close. There are paw prints under each Pokemon (this feature has been temporarily removed). The less paw prints the closer you are to that Pokemon. Select the Pokemon you want to track down and start walking in a straight line, if the Pokemon's paws gets less and less then you are getting closer if the number goes up then your getting further away. Try to narrow it down in a triangular fashion. You can also look at the list of nearby Pokemon to gauge if you are getting closer to it, the higher it is on the list, the closer you are to it in comparison to the other Pokemon on the list.
Tip: If you see fluttering leaves/grass on the map go there first, it could be the Pokemon your looking for.
Click on the Pokemon when you see the Pokemon sitting on the map. Wait a bit for the servers to load and the Pokemon will show up in front of you. You will also see a Pokeball. Tap and hold onto the Pokeball, you will see a green, orange or red circle around the Pokemon start to shrink. If you get the ball in the colored circle you get extra points.
Note: You can get extra points for throwing a curve ball (hold the Pokeball and rotate your finger in a circle to get the ball spinning then throw it). You can loose a lot of Pokeball's trying this so it isn't always worth the few extra points.
Currently you can only catch the first generation Pokemon in Pokemon GO. There is a list being built of all the Pokemon you can catch along with their stats in the guidir Pokemon Go: Pokemon category. Your Pokedex in Pokemon GO only goes up to the highest number Pokemon you've caught in the game e.g. if you catch an Eevee your Pokedex will show up to 133 numbers.
If you've played the traditional Pokemon games it might be a surprise to you when you find a Pokemon and rather than engaging in battle with it, you instead throw a Pokeball at its head and you now own it. But you can still battle! You can use your Pokemon in battle against others in Pokemon GO gyms.
You can click this link to learn all about Pokemon GO gyms or watch the video below to get a good idea on what they are all about. For those not wanting to spend their bandwidth on the video there are bullet points below the videothat summarize gyms are.
Reach level 5 (minimum level to fight in a gym)
Find a gym near you by walking around looking for the icon below
Select the icon and choose to be in one of the three teams. (once you choose you can't change it later on)
If the gym you're at isn't owned by someone in your team you can fight the Pokemon protecting that gym
There can be up to 3 Pokemon you have to fight
Once in battle tap the Pokemon to attack it and swipe to dodge its attacks
If you notice the blue bar in the top left corner is full then hold down your finger on the enemy Pokemon to release your Pokemon's special attack
Once you beat all the Pokemon defending the gym put your Pokemon there to defend it
Pokemon in Pokemon GO don't have Levels like in traditional Pokemon games Instead they have a CP level (Combat Power). The higher your level is, the higher you can raise a Pokemon's CP. To raise a Pokemon's CP you can evolve it and power it up with stardust.
Tip: Don't spend stardust on any Pokemon until you are at least level 20+. A common mistake is spending your limited stardust on Pokemon only to find and capture a wild one with a higher CP later on (which is almost guaranteed because as you become a higher level the wild Pokemon you catch are at a higher CP level).
Evolving: To evolve a Pokemon you need a certain amount of candy for that Pokemon.
Candy: You need candy to power up Pokemon and evolve Pokemon. Each Pokemon has its own candy. Obtain candy from capturing the same Pokemon and also from transferring Pokemon to the professor.
Stardust: Stardust is used to directly power up your Pokemon and raise its CP. You must spend a small amount of Candy to use stardust on a Pokemon. Obtain stardust by capturing Pokemon and being in control of a gym.