1. A persistantly irritating critic or heckler. Someone who constantly criticizes another in an unconstructive manner.
2. A provocateur. Different from the first definition as this one usually implies that the person who is the gadfly in this case is causing others to think or is, in some other way, being constructive by being constant and unignorable. Socrates, for example, is said to have described himself as a gadfly to the Athenian state. Modern day activists could be referred to as gadflies to their opposition.
3. A variety of flies known for pestering livestock and other types of animals, particularly those within the family Tabanidae. Horseflies and breeze flies are examples of such insects. This appears to be the oldest of the three currently used definitions and likely gave birth to the other two through people describing pesky people as these pesky insects.
According to one source1, an early definition of gadfly was "someone who likes to go about, often stopping here and there." This is related to gad, one definition of which is 'to wander.' This definition of gadfly isn't used often these days and some modern dictionaries I've checked have no mention of this definition.
Gadfly, according to several sources1, 2, dates back to 1626. It's from the afore mentioned definition of gad and another definition of the same word meaning a rod or goad that the term gadfly came about, the flies both wandering and being pushy and obnoxious, as would someone poking someone else with a rod. Gad came from the Old Norse gaddr (meaning 'spike,' or 'nail'), which came the Proto-Germanic word gadaz, meaning something along the lines of 'pointed stick.' The 'to wander' portion of the definition is thought to have come from using a gad to be pushy and/or the Old English gædeling, meaning 'wandering.'
A famous mythological gadfly is involved in the story of Io. Io was a mortal the Greek god Zeus fell in love with. To hide his affair from the goddess Hera, Zeus transformed Io into a cow (this was to be temporary) just before Hera discovered them. Hera, suspecting something like this to have occurred, sent a gadfly to constantly annoy the cow. Eventually, after being hounded by the gadfly so long as to nearly go insane, Zeus managed to change Io back to a human.
The American Heritage Dictionary of the English Language, Fourth Edition (via http://www.dictionary.com/)
2Merriam-Webster's Collegiate Dictionary (via http://www.m-w.com/)