Herodians were those who supported Herod Antipas (and possibly also his father when he ruled, as well as his brother), and basically supported him politically, often, as Josephus points out, for personal favours. If it's helpful, thing of them as a lobby group.
The basic political situation at the time was that the Herods ruled judea as client kings of the Roman Empire. Rome allowed the client kings leeway in terms of their ability to rule (i.e. didn't simply place a proconsul or similar in direct positions of power over territory), in exchange for submitting to Roman authority, paying taxes, etc. It was basically a way to smooth over problems after conquest, by allowing some levels of local autonomy.
What is most interesting about Mark 3 is that the idea of the Pharisees and the Herodians teaming up is quite odd behaviour. The Herodians were generally in favour of working with their Roman overlords, because doing so allowed them to retain some measure of status and political power. They viewed Rome from a pragmatic perspective, and possibly saw advantage in the situation for themselves. The Pharisees, for theological reasons, generally opposed the interference of Rome in their affairs, particularly in matters religious (the idea of an unclean and overtly pagan Roman telling God's chose people how to practice their religion would have been abhorrent.)
But here, the Pharisees and the Herodians team up, presumably because they find Jesus to be a threat to not only Pharisaical judaism, but Roman rule. It would be about the equivalent of the Republicans and Democrats teaming up to purse one particular purpose.
The reason Josephus notes Herodians being drowned after the Galilean revolt was because they were seen by many, and most particularly the Zealots (another 'lobby group'), as essentially betraying the Jewish people.