The practice of beating bushes with sticks in order to put hiding birds to flight (so that they can be shot or netted) has given rise to two idioms with similar-sounding formulations but quite different connotations: beat around [or about] the bush and beat the bushes [for].
Dictionary discussions of the idioms
According to Christine Ammer, The American Heritage Dictionary of Idioms (1997), "beat the bushes for" is the older idiom:
beat the bushes for Look everywhere for something or someone, as in I've been beating the bushes for a substitute but haven't had any luck. This term originally alluded to hunting, when beaters were hired to flush birds out of the brush. [1400s]
Another idiom that has much the same meaning (and source in hunting) but arose much later is "scare up," about which Ammer remarks:
The first term ["scare up"] alludes to scare in the sense of "flush game from cover" and dates from the mid-1800s.
As for "beat around the bush," Ammer has this:
beat around the bush Also beat about the bush. Approach indirectly, in a a roundabout way, or too cautiously. For example, Stop beating around the bush—get to the point. This term, first recorded in 1572, originally may have alluded to beating the bushes for game.
In contrast to Ammer, John Ayto, Oxford Dictionary of Idioms, third edition (2009), has no doubt that "beat about the bush" comes from hunting:
beat about the bush discuss a matter without coming to the point; be ineffectual and waste time.
This phrase is a metaphor which originated in the shooting or netting of birds; compare with beat the bushes below.
beat the bushes search thoroughly North American informal
This expression originates from the way in which hunters walk through undergrowth wielding long sticks which are used to force birds or animals out into the open where they can be shot or netted.
So we have an odd situation where the same practical hunting activity has been adopted idiomatically to mean "to take extensive direct action in pursuit of something" and "to take indirect measures to suggest or imply something."
The Cambridge International Book of Idioms (1998) agrees with Ayto as to where "beat the bushes" arose:
beat the bushes American to try very hard to get or achieve something [Example:] She's not out there beating the bushes for a job — she's just as happy not working.
But the North American origin of "beat the bushes," which Oxford and Cambridge agree on, doesn't jibe with the 1400s first occurrence date that Ammer claims. However, in Christine Ammer, The Facts on File Dictionary of Clichés, second edition (2006), Ammer hedges a bit on the 1400s provenance of "beat the bushes," saying that the phrase "has been used in its literal sense since the fifteenth century." That i a far cry, of course, from identifying when it began to be used idiomatically in the sense of "to seek out assiduously."
In her Dictionary of Clichés, Ammer also provides more detail about the earliest occurrence of "beat about the bush":
beat around/about the bush, to Indirection in word or deed; to shillyshally, to approach something in a roundabout way. This expression for overcautiousness dates from the early sixteenth century, when Robert Whytynton (Vulgaria, 1520) warned, "a long betynge about the busshe and losse of time." Some authorities think it came from beating the bushes for game, and indeed there are numerous sayings concerning the delays caused by too much beating and not enough bird catching, dating back even further.
A fuller presentation of the statement by Whytynton (or Whittinton), as cited in Jane Griffiths, John Skelton and Poetic Authority (2006) shows that even at that date the phrase is already being used metaphorically or idiomatically:
Imitacyon of autours without preceptes & rules/is but a longe betynge about the busshe & losse of tyme to a yonge beginner
But Robert Hendrickson, The Facts on File Encyclopedia of Word and Phrase Origins (1997) cites a rather more complicated origin of the term:
beat around the bush. ... Hunters once hired beaters who "started" birds and other game for them by beating the bush and scaring them out into the open. The simplest explanation for the phrase to beat around the bush, to approach a matter very carefully or in a roundabout way, is that these beaters had to take great care when approaching the bush or they would "start" the game too soon for the hunter to get a good shot. But etymologist Ernest Weekley and others believe that the expression, which dates back to at least the early sixteenth century, is a mixed metaphor. Weekley suggests that the old proverb "I will not beat the bush that another may have the bird" joined with "to around the bush," an early expression used for a hound hesitating when circling the bush — and gave us beat around the bush.
Anne Baker, Glossary of Northamptonshire Words and Phrases (1854) offers this interesting local sense of the phrase:
BEAT. "Beat about the bush;" to reconnoitre; to endeavour to obtain information; or attain an object by circuitous means.
Instances of 'beating the bushes' in the wild
Given the early instances of "beating the bushes" and "beating around the bushes" cited by the dictionaries discussed above, one of the most surprising things about a Google Books search for the phrases is how late the earliest matches for each phrase are. Normally when an idiom is in use from the 1500s forward, the Google Books database will include a smattering of instances from the 1600s and many more from the early 1700s. But here, a search for "beat the bushes" turns up only a handful unique and confirmable matches before 1800. The first of these is from Gervase Markham, Hunger's Prevention (1621), cited in the introduction to an 1876 edition of The Tempest, apropos of a description of bat fowling (hunting for roosting birds at night):
Thus being prepared ["with long poales, very rough and bushy at the vpper ends"] and comming into the Bushy, or rough ground where the haunts of Birds are, you shall then first kindle some of your fiers as halfe, or a third part, according as your provision is, and then with your other bushy and rough poales you shall beat the Bushes, Trees, and haunts of the Birds to enforce them to rise, which done you shall see the Birds which are raysed, to flye and play about the lights and flames of the fier, for it is their nature through their amazednesse, and affright at the strangenes of the light and the extreme darknesse round about it, not to depart from it, but as it were almost to scorch their wings in the same; so that those who have the rough bushye poales, may (at their pleasures) beat them down with the same, & so take them.
Also, from James Harrington, The Commonwealth of Oceana (1656):
It is noted out of CICERO by Macchiavel, That the People, tho they are not so prone to find out Truth of themselves, as to follow Custom, or run into Error ; yet if they be shewn Truth, they not only acknowledge and imbrace it very suddenly, but are the most constant and faithful Guardians and Conservators of it. It is your Duty and Office, wherto you are also qualify'd by the Orders of this Commonwealth, to have the People as you have your Hauks and Greyhounds, in Leases and Slips, to range the Fields, and beat the Bushes for them ; for they are of a nature that is never good at this spart, but when you spring or start their proper quarry. Think not that they will stand to ask you what it is, or less know it than your Hauks and Greyhounds do theirs ; but presently make such a flight or course, that a Huntsman may as well undertake to run with his Dogs, or a Falconer to fly with his Hauk, as an Aristocracy at this game to compare with the People.
But the next four are from 1749, 1751, 1755, and 1769, and do not use the phrase metaphorically. From Henry Fielding, The History of Tom Jones, a Foundling (1749):
Western began now to inquire into the original rise of this quarrel [which occurred on the edge of a "thicket"]. To which neither Blifil nor Jones gave any answer ; but Thwackum said surlily, "I believe, the cause is not far off ; if you beat the bushes well, you may find her." "Find her!" replied Western, "what, have you ...
From a letter from "Misocapelus," in The Rambler (April 27, 1751):
My elder Brother was very early initiated in the Chase, and at an Age when other Boys are creeping like Snails unwillingly to School, he could wind the Horn, beat the Bushes, bound over Hedges, and swim Rivers. When the Huntsman one Day broke his Leg, he supplied his Place with equal Abilities, and came home with the Scut in his Hat, amidst the Acclamations of the whole Village.
From Dr. Hoadly, The Suspicious Husband (1755):
Frank. ... Dear Bellamy, I know your concern for me. See her first, and then blame me if you can.
Bellamy So far from blaming you, Charles, that, if my endeavours can be serviceable, I will beat the bushes with you.
Frank. That, I am afraid, will not do. For you know less of her than I. But if in your walks you meet a finer woman than ordinary, let her not escape till I have seen her.—Wheresoe'er she is, she cannot long lie hid.
And from a review quoting from Tobias Smollett, The History and Adventures of an Atom, in The Monthly Review (June 1769):
The president Soo-san-sin-o, took notice, that if there had been one spaniel in the whole Japonese army, this disaster [a successful ambush by Chinese fighters] would not have happened ; as the animal would have beat the bushes and discovered the ambuscade.
The Rambler and Smollett examples above are interesting because they explicitly refer to "beating the bushes" as being a task performed not by paid human workers but by trained greyhounds and spaniels. But the Fielding and Hoadley examples involve human beaters.
The earliest nonliteral use of "beat the bushes" (after Harrington's from 1656) in the Google Books search results occurs in the late 1800s. On the strength of this record, it's hard to see why Ammer, Ayto, and Cambridge consider "beat the bushes" a North American idiom.
Instances of 'beating about/around the bush' in the wild
The two earliest instance of "beat about the bush" in Google Books search results are from 1821 and 1822. From E. H. McLeod, Tales of Ton (1821):
"Well then, it is a queer thing to do ; but I will sound, I will beat about the bush, if I could see her alone ; I have a little penetration, and I should soon know; for it is an awkward thing to be refused — a devilish awkward thing, upon my soul!"
and from Niles' Weekly Register (March 2, 1822):
Though it is to me, personally, a matter of perfect indifference, an error of opinion prevails that I wish to correct: the remarks made in this work on the finances of the United States, have been construed into acts of hostility to the head of the treasury department. It is not consistent with my principles or practice thus to "beat about the bush;" and the whole purpose that we had in speaking of treasury matters, was to shew the defects of the system—wretchedly managed, perhaps, from its own wretched nature.
A decade later, from John Taylor, Records of My Life (1833):
[Thomas] King possessed a shrewd mind, and copied his characters from real life, and from manners of any of his predecessors. He was admirable in story telling in private company, and when any persons beat about the bush to draw from him a particular story, he always stopped them and said, "I see what you are at, don't give yourself any trouble," and he would then to tell a facetious anecdote, which required some degree of acting, as if it was some narrative of the day.
Another early instance is from Thomas James, Six Months in South Australia: With Some Account of Port Philip and Portland Bay, in Australia Felix; With Advice to Emigrants (1838):
Persons, all indeed who could be spared, were now called away from their usual duties, and as many were mounted on horseback as they could manage, and they beat about the bush for several days, shouting and lighting fires, to attract the notice of the straggler.
Here off course, the meaning is literal, not idiomatic, except perhaps in the sense of "wandering about in search of someone or something lost in the bush, making noise and setting fires as signals"—but it is quite different from the idea of forcing prey to flee from hiding places in tress or underbrush. That meaning pops up (metaphorically) in James St. John, The History of the Manners and Customs of Ancient Greece, volume 2 (1842):
A crown, an extra junket, and the applause of the company, cheered the successful Œdipos [in riddle-solving contests], while the lackwit who beat about the bush without catching the owl, had to make wry faces over a cup of brine or pickle.
But the generalized idiom returns, very modern in tone, in Charles Dickens, The Old Curiosity Shop, in Master Humphrey's Clock (1841):
The girl [little Nell] has strong affections, and, brought up as she has been, may at her age be easily influenced and persuaded. If I take her in hand, I will be bound, by a very little coaxing and threatening, to bend her to my will. Not to beat about the bush (for the advantages of the scheme would take a week to tell), what's to prevent your marrying her?"
"Beat around the bush" appears to have been (initially at least) a U.S. variant of "beat about the bush." It first shows up in Google Books search results in books from the 1860s. From The Congressional Globe, volume 32, part 3 (1862) [snippet]:
Now, sir, where is the constitutional provision? What does it amount to? Is it not worse than a mockery? If we intend to do this, let us do it directly; let us march up manfully to it, not beat around the bush, not evade it, but walk up to it and say that notwithstanding the provision, it was unwisely made, and we will put our heel upon it and crush it out of the Constitution.
And from "Notabilia," in The Examiner (August 19, 1865):
MEXICO.—Advices received in New York state that Lopez had defeated Cortenas, and the latter had fled to the Texas side of the river. During an entertainment given to the Republican Mexican General Ortega, in New York, on the 3rd inst., the following extract from a letter from General Sheridan, commanding the Federal troops on the Rio Grande, was read : "It is of no use to beat around the bush in this Mexican matter; we should give a permanent Government to that Republic. Our work in crushing the rebellion will not be done until this takes place.
Though authorities find instances of beating the bushes and beating about/around the bush" that go back at least four centuries, neither expression seems to have been especially common in published works between roughly 1660 and 1750 (in the case of "beat the bushes") and not until the 1820s for "bear about the bush"; "beat around the bush" begins to appear some 40 years after that.
Some of the examples suggest that all three expressions may have a common root meaning of flushing prey out of hiding, but the separation into the meanings "expend considerable effort on" and "ask or seek information indirectly" seems to have happened early in the 1800s usage of "beat about the bush."