To access the Random Match part of the game, talk to the attendant on the right on the top floor of each Pokémon Centre. Random Match will be an option under the GTS. Here, you can go in and select the various Random Match styles you want. You'll be able to play with people over WiFi who aren't in your friends list.

Rules
Pokémon of Level 51 or above are lowered to Level 50 while those under Level 50 will remain their current level
You cannot have two of the same Pokémon or item in your team
Items that aren't available in Generation V as of yet, including event Berries, cannot be used
No Pokémon with the move Sky Drop can be used
Two minutes to decide upon the moves to use
Matches last no more than one hour

Battle Styles
Single Battle - Use 3 Pokémon
Double Battle - Use 4 Pokémon
Triple Battle - Use 6 Pokémon
Rotation Battle - Use 3 Pokémon
Shooter Battle - Use 6 Pokémon in a Triple Battle

Random Match Modes
Rating Mode - Uses your battle stats to be included in the Battle Union's ranking system. Requires Global Link syncing
Free Mode - Only tracks your Win/Loss for your Trainer Card

Not all Pokémon are usable in the Random Match feature with almost all legendary Pokémon banned. The list of the Pokémon which cannot be used is as follows:

No.	Pic	Name	Type	Abilities	Base Stats
					HP	Att	Def	S.Att	S.Def	Spd
#150		Mewtwo ミュウツー		Pressure Unnerve PDW	106	110	90	154	90	130
#151		Mew ミュウ		Synchronize	100	100	100	100	100	100
#249		Lugia ルギア		Pressure Multiscale PDW	106	90	130	90	154	110
#250		Ho-oh ホウオウ		Pressure Regenerator PDW	106	130	90	110	154	90
#251		Celebi セレビィ		Natural Cure	100	100	100	100	100	100
#382		Kyogre カイオーガ		Drizzle	100	100	90	150	140	90
#383		Groudon グラードン		Drought	100	150	140	100	90	90
#384		Rayquaza レックウザ		Air Lock	105	150	90	150	90	95
#385		Jirachi ジラーチ		Serene Grace	100	100	100	100	100	100
#386		Deoxys デオキシス		Pressure	50	150	50	150	50	150
#441		Chatot ペラップ		Keen Eye Tangled Feet Big Pecks PDW	76	65	45	92	42	91
#483		Dialga ディアルガ		Pressure Telepathy PDW	100	120	120	150	100	90
#484		Palkia パルキア		Pressure Telepathy PDW	90	120	100	150	120	100
#487		Giratina ギラティナ		Pressure Telepathy PDW	150	100	120	100	120	90
#489		Phione フィオネ		Hydration	80	80	80	80	80	80
#490		Manaphy マナフィ		Hydration	100	100	100	100	100	100
#491		Darkrai ダークライ		Bad Dreams	70	90	90	135	90	125
#492		Shaymin シェイミ		Natural Cure	100	100	100	100	100	100
#493		Arceus アルセウス		Multitype	120	120	120	120	120	120
#494		Victini ビクティニ		Victory Star	100	100	100	100	100	100
#643		Reshiram レシラム		Turboblaze	100	120	100	150	120	90
#644		Zekrom ゼクロム		Teravolt	100	150	120	120	100	90
#646		Kyurem キュレム		Pressure	125	130	90	130	90	95
#647		Keldeo ケルディオ		Justified	91	72	90	129	90	108
#648		Meloetta メロエッタ		Serene Grace	100	77	77	128	128	90
#649		Genesect ゲノセクト		Download	71	120	95	120	95	99