After you start a new HeartGold or SoulSilver game, you can read some information about the game's controls. After that, Professor Oak will tell you all about Pokémon. Then you can choose to play as the boy or girl character. As far as I know, the only difference in gameplay for choosing boy or girl is that people might say slightly different things in some places, but it doesn't make much of a difference.
Once you choose which character to play, you can set your name, and then the game begins.
You start out in your room and you can check email on your computer. You will have email from the character of the opposite gender (i.e. if you play as Lyra, you have email from Ethan; if you play as Ethan, you have email from Lyra).
Go downstairs and talk to Mom to learn that Professor Elm was looking for you. Go next door to Professor Elm's lab. He'll talk to you, and then he'll get an email from Mr. Pokémon, who found a pokémon egg. Elm asks you to go get the Egg for him.
Now, save your game. You can go over to the table with the three Pokéballs. These contain the three starter pokémon, and you can choose one. Their natures and genders are determined when you go over to look at them, so if you want to get something different from what you get, you'll have to turn off the game and reset until you get the type that you want.
Choose whichever Pokémon you want. There is Chikorita (grass), Cyndaquil (fire), and Totodile (water). Give it a nickname if you wish. Later on in the game you reach a point where you can change the nickname, but it does take a while to get there.
You can heal up your Pokémon using Elm's computer.
Go talk to Mom to get the all-important Pokégear. She'll explain how to use it.
Head west, getting Elm's phone number for your Pokégear as you leave. Then you can exit New Bark Town and make your way toward Mr. Pokémon's house.