What are its origins and what does it really mean?
The concept behind the phrase is that some areas of life are so important and overwhelming that you cannot blame someone for acting in their own best interest. For war, this implies that spies, torture, lying, backstabbing, making deals with enemies, selling out allies, bombing civilians, wounding instead of killing, and so on are "fair game" in the sense that by taking these options off of the table you are only hurting yourself: Your opponent has no reason to comply to your moral standards. (This entire concept is mostly void with regards to the current political atmosphere of Earth. Countries have actually declared certain things taboo with regards to war — with mixed success.)
The point of adding love to the list is likely to compare it to war. There are two main subtexts here. The first and most relevant is the idea that you can wreak all the havoc you want during the pursuit of true love. This includes sabotaging the third side in a love triangle or using deceit and trickery to woo the object of your affection (including hiding past lovers from them).
The second is the viewpoint that ongoing love between two people is akin to a battle that results in a dominant winner. The stereotypical gender wars are similar to this. A man and woman are in love, but a certain unease comes with the territory, and pulling one over on your spouse is fair game because, in the end, all is fair in love and war. For what it is worth, this last point is probably more of a causality (i.e., an unintended, natural consequence) of the individual words in the phrase than any original intended meaning. Most people probably don't immediately think of this type of behavior as matching up with the phrase until after they need an excuse for their actions.
I don't think anyone has addressed (more than cursorily, anyway) the part of the poster's question that asks, "What are its origins?"—so I'll focus on answering that. J. A. Simpson, The Concise Oxford Dictionary of Proverbs (1982) offers this lineage for the proverb:
All's fair in love and war
[1578 LYLY Euphues I. 236 Anye impietie may lawfully be committed in loue, which is lawlesse.] 1620 T. SHELTON tr. Cervantes' Don Quixote II. xxi. Love and warre are all one. .. It is lawfull to use sleights and stratagems to .. attaine the wished end. 1845 G. P. R. JAMES Smuggler II. iv. In love and war, every strategem is fair, they say. 1850 F. E. SMEDLEY Frank Fairlegh xlix. "You opened the letter!' .. 'How was I to read it if I hadn't? All's .. fair in love and war, you know.' 1972 J. I. M. STEWART Palace of Art xii. 'Do you really suppose I would tell?' he demanded coldly. 'Might do. All's fair in——.'
But between Shelton in 1620 and James in 1845, an interesting alternative commentary on love and war was developing in North America. From Bartlett Whiting, Early American Proverbs and Proverbial Phrases (1977):
L230 In Love and war no time should be lost
1777 Munford Patriots 451: In love and war no time should be lost. 1784 Washington Writings 28.2: Favorable moments in war, as in love, once lost are seldom regained.
Martin Manser, The Facts on File Dictionary of Proverbs (2002) cites the Smedley quotation from 1850 as the first instance of the proverb in its current standard form, but then notes:
The proverb was first recorded with different wording, in 1620 [presumably meaning Shelton's translation of Don Quixote]. In modern use an extra word is often added to or substituted for part of the proverb, as in "All's fair in love—an' war—an' politics" (George Ade, County Chairman, 1903).
Linda and Roger Flavell, Dictionary of Proverbs and Their Origins (1993) offers this longer view of "all's fair in love and war":
The assumption behind this proverb is that the end justifies the means.This has long been recognized in the theatre of war. Livy hinted at it two millennia ago: To those to whom war is necessary it is just (HISTORY c 10 BC). Courtship, too, may entail the use of any means if one is to emerge victorious and take the prize. These excesses of the heart are considered forgiveable because love has long been understood as a force which cannot be restrained: Both might and malice, deceyte and treacherye, all periurye, anye impietie may lawfully be committed in loue, which is lawlesse (John Lyly, EUPHUES, 1579).
The link between love and fighting for a kingdom was already established in a proverbial form by 1606: An old saw hath bin, Faith's breach for love and kingdoms is no sin (Marston, THE FAWN). Later in the same century Aphra Behn writes: Advantages are lawful in love and war (THE EMPEROR AND THE MOON, 1677). There was also the strong contemporary influence of DON QUIXOTE by Cervantes. Publication of Part One was in 1605 and it was soon translated into English. One passage runs [in Spanish, literally translated, presumably, since this isn't Stewart's language]: Love and war are the same thing, and stratagems and policy are as allowable in the one as in the other.
Rosalind Fergusson, The Facts on File Dictionary of Proverbs (1983)—same title and publisher as Manser's book above, but almost twenty years older and completely different in content—identifies several allied proverbs, though it doesn't identify where these other sayings come from:
Love is lawless.
Love is a game in which both players always cheat.
War, hunting, and love are as full of trouble as pleasure.
Advise none to marry or to go to war.
I'll paste the definition given by the OALD because it's clearer than how I may say it: "In some situations any type of behaviour is acceptable to get what you want", i.e. you can be as deceitful, dishonest and false as you want in war and love.