The rules of this game are well explained in "Rules for my favorite version of Hearts". I especially like the variant "Omnibus Hearts" which is summarized here:
Every card of Hearts is worth 1 point, the Queen of Spades is worth 13 points while the Jack of Diamonds counts -10. (By the way, the aim of the game is to have as little points as possible). Before the game starts you exchange 3 cards with another player. The player with the 2 of Clubs begins a new round, the other players have to follow suit (if possible). In the first round you must not play a card that is worth points and you must not begin a new round with a card of Hearts unless someone has played Hearts already. BUT: If a player gets all Hearts and the Queen of Spades, he "shot the moon"; then all other players get 26 points.
For Linux I found only two programs: This one (requires Qt and KDE) and xhearts (from 1993!), but none of them compiled on my system. So I took the sources of xhearts (thanks to Bob Ankeney, Mike Yang, Don Baccus and Jeff Hemmerling), removed the network support and made a new GUI with the FOX toolkit. It works and is fun to play.
See here for a screenshot