Actually you don't even need to get that many votes. Depending on the electoral system you might not need to win a majority of the votes in any constituency, you just need more votes than anyone else, which could be a very low percentage if the opposition is split enough ways.
The current governing party in the UK holds a comfortable majority of seats despite only winning 43% of the vote in the last election. And in fact, this was the highest vote share received by any party in decades. Labour in 1997 won more seats on a lower vote share.
> Weren't some of the sates basically only created to give a certain party the majority?
I've read that the reason Dakota Territory was split in two (North and South) upon statehood was mainly as a cynical ploy to get two extra senate seats for the favoured party.