How was library classification done in English-speaking libraries prior to the 19th century?

This question is rather broad so this is no more than an overview of the period 1640 to 1850 with a few specific examples.

The short answer is books were most commonly organized on shelves by one or (most likely) more of the following: subject, format / size, alphabetically by author or title (though titles were often abbreviated so this sometimes wasn't much help). Other factors, such the architecture of the building, could also influence how books were shelved. Also, some collections were much better organized than others. Some were well-catalogued and kept up-to-date, others were not.

Referring to the period 1640 - 1750

Baroque librarians inherited, and largely failed to supersede, a system based on three principles: fixed location, collocation by format (effectually shelving by height), and subject division derived from the medieval curriculum.

Source: P. Morrish, 'Baroque Librarianship', chapter 14 in 'The Cambridge History of Libraries in Britain and Ireland' (vol.2)

Morrish explains further, mentioning both practicality and 'harmony':

Practicality and aesthetics justified shelving by format. It was economical of vertical space and also ergonomic because removal of folios from lower shelves is less laborious than from higher. Moreover, promiscuous shelving of taller books with shorter deprives the taller of adequate lateral support (they may collapse) and the shorter may slip from view. Then the baroque eye sought harmony. A shelf of duodecimos appeared incongruous under a shelf of folios, whilst gradation from taller books at the bottom to shorter ones at the top gave an illusion of height to a room. Thus Wren’s drawings for the library at Trinity, Cambridge, show the two bottom shelves at 22-inch centres, the next at eighteen and the top two at fourteen.

Architecture and subject also played important roles in how books were arranged:

Medieval subject division had been fourfold – arts, law, medicine and theology....Theology was pre-eminent, but actual distribution of these subjects in a room might depend as much upon architectural constraints as upon academic protocol.

Finding subjects was not necessarily difficult as

names might appear on the open end of every case, either painted or on a small wooden plaque (tabula) fixed there. In a wall library, names might appear on the architraves of cases.

All this worked reasonably well with collections that were 'static' (and where there was a catalogue) but mostly they were expanding and this, combined with 'shelving by format' (larger volumes were placed on bottom shelves) made it difficult for visitors to find anything. Catalogues were thus essential.

Each book bore a unique press-mark, usually letters and numbers, which established its settled place. A typical mark might appear as ‘12.a.3’, that is, the third book from the left on shelf ‘A’ in the twelfth case. Each shelf and case would bear corresponding notation, and each book a spine-label...showing its full press-mark.

Source: Morrish

Referring to universities in the period 1750 to 1850:

Even in 1850 modern library classification was still some twenty years in the future, but the formal classification of knowledge was well under way...

Most libraries were shelved in some kind of subject arrangement, but most locations were fixed and related to the cases and rooms in which the books were housed. The rational expansion of any subject sequence required extensive physical rearrangement. Many, if not all, volumes in the expanded sections needed to be given new shelf-marks or press-marks, and catalogues, be they printed or manuscript, laboriously updated. However, early attempts at classified arrangements of collections, with related subdivisions of basic divisions, can be found in libraries like that of Anderson’s University, divided into four divisions of theology, philosophy, literature and history which were themselves subdivided and further subdivided again; philosophy included what later generations would call the social sciences, physical and natural sciences, and the arts.

Source: Peter Freshwater, 'Books and Universities', chapter 22 in 'The Cambridge History of Libraries in Britain and Ireland' (vol.2)

The library at All Souls College, Oxford, moved into a new building in 1751 where books were

organised by a subject classification with alphabetical and class catalogues....The bookcases were arranged along the north side on two levels, and on one level on the south.

Ecclesiastical libraries are harder to generalize about. Some were well-maintained, others neglected, and 1750 - 1850 was also a time when libraries were being moved from one location to another. However,

This was a great age for making catalogues, often in several versions: Gloucester had at least three between 1760 and 1833. The preferred formula seems to have been a fully descriptive shelflist accompanied by an alphabetical index. Most of these were still in manuscript, but the first printed catalogues in these libraries also date from this period, the earliest being that of 1802 at Canterbury based on the work of Henry John Todd. This was a model of its kind, providing in one volume a shelflist with an alphabetical index.

Source: Joan Williams, 'Ecclesiastical libraries', chapter 20 in 'The Cambridge History of Libraries in Britain and Ireland' (vol.2)

The Cotton Library

As suggested by Mark Olsen in his comment below, Sir Robert Cotton (1570/1 – 1631) and the Cotton Library is well worth a mention:

Sir Robert Cotton had organised his library according to the case, shelf and position of a book within a room twenty-six feet long and six feet wide. Each bookcase in his library was surmounted by a bust of a historical personage, including Augustus Caesar, Cleopatra, Julius Caesar, Nero, Otho, and Vespasian. In total, he had fourteen busts, and his scheme involved a designation of bust name/shelf letter/volume number from left end. Thus, the two most famous of the manuscripts from the Cotton library are "Cotton Vitellius A.xv" and "Cotton Nero A.x". In Cotton's own day, that meant "Under the bust of Vitellius, top shelf (A), and count fifteen over" for the volume containing the Nowell Codex (including Beowulf) and "Go to the bust of Nero, top shelf, tenth book" for the manuscript containing all the works of the Pearl Poet. The manuscripts are still catalogued by these call numbers in the British Library.

The Cotton library "later became the basis of what is now the British Library". More details can be found the British Library site's article Cotton manuscripts.