Starter's guide to building Battle Maison teams for long streaks
1. Pick a team you like from the leaderboards at
http://spo.ink/maison (Smogon's Battle Maison thread). Any mode will do, but I recommend Singles (without Durant Entrainment) to get started.
Copy it and play while consulting Maison set data (found at
http://spo.ink/maisonspreadsheet ) to see what you're up against. You mostly face Set4s after Battle 40. Veterans (who use Legendary Pokémon) are the biggest exception, and can use multiple sets - consult the trainer list and use the search function in the spreadsheet for specifics. Damage calcs are also useful.
Don't look up Maison data in battles 1-40, as most of the sets seen in those battles don't appear after battle 40. With the succesful team you're using, you should breeze past the early rounds most of the time.
2. Play the team for a few hundred battles past battle 40.
Be sure to look up AI sets all the time.
If you lose, try again. See if you could've won the battle by playing differently. The mock battle function in VS Recorder is useful.
3. After completing steps 1 and 2, you now know basics about the kind of opposition you face in the Maison, and can try building a team of your own with your new-found skill and experience.
Scavenge ideas from the Smogon thread. Put them on different teams. Try a different mode. Keep consulting the Maison set data whenever you're not sure.
Why? When you are new to the Maison, you are in a catch-22: you need a team to play the Maison and make it far past battle 40 with, and you need Maison experience and skill to build that team. Using an established team gets you into the heart of the Maison right away. Once you've learned the basics, you are in a much better position to build your own team.