The Coliseum is on the west side of Atlantea on the Campaign Map. You can access it as soon as you've beaten the Orc Encampment mission, which is available to new players almost immediately.
Every day (every 22 hours to be exact), a new set of 30 warlords appears in the Coliseum to challenge you to battle! You fight increasingly difficult opponents as you go along. You have 30 tries to beat 20 of the warlords. When the Coliseum closes at the end of the day (when the timer is up), you will receive a prize of 1 Gem per warlord you've beaten, plus a special bonus of 5 Gems if you max out 20 victories (for a possible total of 25 Gems per day).
The Coliseum may look like it’s PvP but it’s actually PvE. The way it works is that when you enter for the first time every day, the game takes a snapshot of the decks of many other players, and it uses those decks for the warlords you will fight. However, as of that moment the opponents are fixed (so if they change their decks it won't affect your opponents in the Coliseum). Even though other players may also fight in the Coliseum, each player has his own instance fighting against static decks, so you never have to worry about other players beating your deck and counting against you. This also means that every single player, if he spends enough time, can achieve the top prize daily (although it can be a bit of a grind!)
There is no penalty for losing fights, and you will gain gold and experience for victories as usual. This is generally a great place to practice, and to earn some Gems, while you are waiting for chests to open in your Treasures screen or want to take a break from grinding other content.
PRO TIP: The Coliseum is the minigame that pro players use to grind for Gems daily. Once you have a decent deck and some patience most players can earn upwards of 150 Gems a week this way!