There are ten companions in Ikoria, each one a legendary creature whose companion ability lists a deck-building rule. If your starting deck follows that rule, then the legendary creature can serve as your chosen companion.
You can have up to one chosen companion for each game. That chosen companion doesn't start in your main deck. Rather, it's a card in your sideboard. (If you're playing casually without sideboards, it's just in your collection outside the game. All the same rules apply to it.) This means it doesn't count as a card toward meeting the minimum deck size in the format you're playing, but in Constructed formats, it is one of your fifteen sideboard cards.
Just before the game begins, reveal your chosen companion to all players. Once during the game, you may cast your chosen companion from your sideboard. Doing so follows all the normal rules for casting a creature spell, so do so only during your main phase.
Casting your chosen companion brings it onto the game for good. The spell will go on the stack. If it resolves, it will enter the battlefield under your control. If it's countered, it will go to your graveyard. Once it's in the game, it can be exiled, go back to your hand, be shuffled into your library, etc. It won't return to your sideboard until the game ends.
Your companion's deckbuilding rule applies only to your starting deck, which is the deck you begin play with each game. It won't consider any cards in your sideboard, so those cards don't have to follow the deck-building rule. Additionally, you can just ignore the deck-building rule and include creature cards with companion in your main deck. This is especially relevant to formats like Booster Draft, where following the deck-building rule may not be possible. But if you can pull it off, glory awaits.
Each Historic Brawl deck may include a chosen companion. It starts outside the game and doesn't count as one of your 100 cards. Just like the rest of your deck, your commander must follow the deck-building rule if you're going to use a companion.
New Companion Rule (Announced June 1, 2020)
Once per game, any time you could cast a sorcery (during your main phase when the stack is empty), you can pay 3 generic mana to put your companion from your sideboard into your hand. This is a special action, not an activated ability.
Additional information on this rule update can be found here in our June 1, 2020 Banned and Restricted Announcement.