From Bulbapedia, the community-driven Pokémon encyclopedia.
Opening and VS Willie
From the main menu, create a new game. Choose your name. Your name can be Wes, Seth, Thomas, or a custom name. Watch the intro, which involves Wes exploding and escaping Team Snagem's hideout with Umbreon and Espeon. That big strong guy with the mustache is Gonzap, you'll be seeing him later. So here are your first two Pokémon. If you're unfamiliar with these games, see about the basic details of Pokémon Colosseum such as gameplay, mechanics and what-not.
You'll arrive at this bar in the middle of nowhere. You'll see two guys leave the bar, do chit-chat, and leave in a car. Enter the bar, talk to the barman, and watch the television. It tells you what just happened. Talk to the guy at the very end of the bar. When he asks you a question, answer "YES". Then leave the bar. He'll follow you, and tell him that his name's Willie. Agree to his battle request, and have your first battle.
Level 24 Zigzagoon
Level 24 Zigzagoon
Rider Willie is an easy battle. You should be able to win with your basic attacks without any trouble. Just to note for later, Umbreon's strongest move right now is Bite, and Espeon's is Confusion.
He'll tell you to "sharpen your skills" at Phenac City. Go to the map (by leaving the border of the area) and Phenac City is easily viewable on the map. Select it and ride to it.
Upon arrival you'll see two grunts kidnapping someone. They see you, drop the sack and you figure out that a human is in there! They walk over to you and challenge you to a battle.
Shady Guy Folly
Level 24 Whismur
Level 25 Whismur
A Confusion or two Bites on each should do the trick. Another pushover. You think they'd assign a kidnapping job to someone who has actual good Pokémon.
After some dialogue, the grunts leave and you help two citizens of the city free the bag. (You must walk up to the sack and undo the rope (by answering "YES", of course). It frees Rui, someone who will tag along with you the entire game. She has the uncanny ability to spot Shadow Pokémon. You don't learn this until later when it becomes important. You can name her Rui, Anca, Yuki, or your own name, but for the sake of simplicity, let's just call her Rui throughout the guide. More dialogue, and you'll find out where the mayor is. If you're too lazy to read it, just circle the fountain, go up the stairs, and take a left.
Before you enter, a man with long gray hair comes out. He talks to you, pays to mind to you, and walks away. He'll be important later. Enter the building and talk to Es Cade, the portly mayor with interesting hair . You'll learn about Shadow Pokémon a little bit, and the mayor tells you to go to the Pokémon Stadium. Go up the next flight of stairs and you'll enter the Pokémon Stadium.