c. 1200, "thick stick wielded in the hand and used as a weapon," from Old Norse klubba "cudgel" or a similar Scandinavian source (compare Swedish klubba, Danish klubbe), assimilated from Proto-Germanic *klumbon and related to clump (n.). Old English words for this were sagol, cycgel. Specific sense of "bat or staff used in games" is from mid-15c.
The club suit in the deck of cards (1560s) bears the correct name (Spanish basto, Italian bastone), but the pattern adopted on English decks is the French trefoil. Compare Danish klr, Dutch klaver "a club at cards," literally "a clover."
The sense "company of persons organized to meet for social intercourse or to promote some common object" (1660s) apparently evolved from this word from the verbal sense "gather in a club-like mass" (1620s), then, as a noun, "association of people" (1640s).
We now use the word clubbe for a sodality in a tavern. [John Aubrey, 1659]
Admission to membership of clubs is commonly by ballot. Clubs are now an important feature of social life in all large cities, many of them occupying large buildings containing reading-rooms, libraries, restaurants, etc. [Century Dictionary, 1902]
I got a good mind to join a club and beat you over the head with it. [Rufus T. Firefly]
Join the club "become one of a number of people having a common experience" is by 1944. Club soda is by 1881, originally a proprietary name (Cantrell & Cochrane, Dublin). Club car is from 1890, American English, originally one well-appointed and reserved for members of a club run by the railway company; later of any railway car fitted with chairs instead of benches and other amenities (1917). Hence club for "class of fares between first-class and transit" (1978).
The club car is one of the most elaborate developments of the entire Commuter idea. It is a comfortable coach, which is rented to a group of responsible men coming either from a single point or a chain of contiguous points. The railroad charges from $250 to $300 a month for the use of this car in addition to the commutation fares, and the "club" arranges dues to cover this cost and the cost of such attendants and supplies as it may elect to place on its roving house. [Edward Hungerford, "The Modern Railroad," 1911]
Club sandwich recorded by 1899 (said to have been invented at Saratoga Country Club in New York), apparently as a type of sandwich served in clubs, or else because its multiple "decks" reminded people of two-decker club cars on railroads.