Etymonline indicates that the "completely" sense of the word was an extension of the "exact measurement" sense of the word and dates this shift back to the mid-18th:
c.1300, "lead hung on a string to show the vertical line," from O.Fr. *plombe, plomme "sounding lead," from L.L. *plumba, originally pl. of L. plumbum "lead," the metal, of unknown origin, related to Gk. molybdos "lead" (dial. bolimos), probably from an extinct Mediterranean language, perhaps Iberian. The verb is first recorded late 14c., with sense "to immerse;" meaning "take soundings with a plumb" is first recorded 1560s; figurative sense of "to get to the bottom of" is from 1590s. Plumb-bob is from 1835. Adj. sense of "perpendicular, vertical" is from mid-15c.; the notion of "exact measurement" led to extended sense of "completely, downright" (1748), sometimes spelled plump or plunk.
Edit re: British vs. American use:
I found this newsletter on British plumb bobs and noticed that another word used for the tool in several publications was plummet rather than plumb-bob. Perhaps plummet was a common enough name for the tool in England that it prevented the development of the extended sense of plumb as occurred in the U.S. This is only a guess.
Edit re: confusion with plum:
After seeing the OED references in @Simon's answer, I agree with @Peter's comment that there seems to be some confusion between the etymology of plumb and plum as intensifiers. I found this on plum at Etymonline:
O.E. plume, early Gmc. borrowing (cf. M.Du. prume, O.H.G. phruma, Ger. Pflaume) from V.L. *pruna, from L. prunum "plum," from Gk. prounon, later form of proumnon, from an Asiatic language. Change of pr- to pl- is unique to Gmc. Meaning "something desirable" is first recorded 1780, probably in ref. to the sugar-rich bits of a plum pudding, etc.
Some of the OED references seem to be examples of plum being used to mean "something desirable" rather than misspellings of plumb meaning "completely."