The Battle Tower can be found only in the Crystal version, west of Olivine City. Go into the house, and you'll find yourself standing in front of a tall structure filled with trainers. Before you enter, make sure that you have three Pokemon and only three Pokemon.
In the Japanese version, you'll need to have a Mobile GB Adaptor to enter, but in the English version, anyone can enter (since there is no Mobile GB Adaptor). Upon entering, talk to the receptionist. You'll be asked to take in with you only three Pokemon (as I've said). If you have more or less than three Pokemon, you won't be able to go on any further. You'll also need to choose the rules that you'll play by. For example, if I had a level 45 Typhlosion, then I'll have to go to the level 50 room, not level 40. Then, you are taken up the floors by an elevator to the floor with the level that fits you.
The levels of the Pokemon varies from 10 - 100! You cannot use any items (remember, that means no Potions), but attachments (such as Quick Claw) are allowed. You won't gain any experience points by battling here. There are ten floors in the Battle Tower, and seven trainers on each floor. That makes 70 trainers! You won't be battling all of them, though. You only battle on the floor of the level that was selected. If you defeat all the trainers in one challenge area, you'll get a prize.
Here's an image that shows a prize that you can get.
In this case, it is five Calciums.
The trainers here are very tough, and only the best can defeat them. They use a lot of items, and can crush you like a bug if you aren't experienced enough. So, be prepared for the fight of your life!