The phrase cleanliness is next to godliness, and variants, mean that physical cleanliness betokens spiritual purity—i.e., that cleanliness proceeds from piety.

Before this phrase came into use, the English statesman and philosopher Francis Bacon (1561-1626) had expressed the same idea in The Two Bookes of Francis Bacon. Of the proficience and aduancement of Learning, diuine and humane (London: Printed for Henrie Tomes, and are to be sould at his shop at Graies Inne gate in Holborne, 1605):

For Cosmetique, it hath parts Ciuile, and parts Effeminate : for cleanesse of bodie, was euer esteemed to proceede from a due reuerence to God, to societie, and to our selues. As for artificiall decoration, it is well worthy of the desiciences [sic] which it hath : being neither fine inough to deceiue, nor handsome to vse, nor wholesome to please.

It is generally said that the phrase cleanliness is next to godliness was coined, or at least first used, by the English preacher and co-founder of Methodism John Wesley (1703-1791) in his sermon On Dress [note 1]. This is probably because the earliest occurrence of the phrase that the Oxford English Dictionary (1^st edition, 1889) has recorded is from this sermon.
—The following is from the earliest edition of this sermon that I have found, i.e., from The Works of the Rev. John Wesley (London: Printed […] by Thomas Cordeux […], 1811):

Let it be observed, That Slovenliness is no part of Religion : that neither this, nor any text of Scripture, condemns neatness of apparel : certainly this is a duty : not a sin : “Cleanliness is, indeed, next to godliness.”

However (if the numerous editions of this sermon are to be relied upon), “Cleanliness is, indeed, next to godliness” is in quotation marks, which suggests that John Wesley was using a phrase that already existed.

In fact, the texts containing the earliest occurrences of the phrase cleanliness is next to godliness, and variants, neither corroborate nor invalidate the theory that it was John Wesley who coined, or first used, the phrase.

These are, in chronological order, the earliest occurrences of the phrase cleanliness is next to godliness, and variants, that I have found:

1-: From a footnote to Leviticus, Chapter XXVII, V. 34., in The Holy Bible, containing the Old and New Testament. With Notes (London: Printed for W. Davis […], G. Kearsly […], [&c.], 1773), by the English churchman Anselm Bayly (1719-1794):

Cleanliness, it is rightly said, is next to godliness; but the numberless washings, expiations and purifications of the Jews were superfluous to this end, and troublesome to the body, and therefore are by necessity transferrable to the mind: hence again, “Make me a clean heart, O God! and renew a right spirit within me.”

2-: From An Essay on Tea, Sugar, White Bread and Butter, Country Alehouses, Strong Beer and Geneva, and other Modern Luxuries (Salisbury: Printed and Sold by J. Hodson, 1777):

It is a most notorious truth, that virtuous industry will accomplish most surprizing performances. How often do we find, that labour properly exerted, and employed by man and wife, will by the sweat of the brow, joined to œconomy and cleanliness, preserve a family of six children from the parish; whereas the negligence, the dissipation, and dirtiness of another pair, under just the same circumstances, with regard to their support in life, viz. that of a good constitution, and the labour of their hands, will oblige them to apply to the Overseers for relief, even although they have not more than half, nay not more than two to maintain? I mention cleanliness as an essential circumstance of a good housekeeper, and the utility and good effects of it, in the conduct of a family, are more and greater than can easily be imagined. To a poor man, it makes his home healthful, and consequently prevents the disorders which always attend squalid sluttishness. It makes the house more chearful, and therefore more pleasing to the inhabitants: in a word, it makes the husband to delight in staying at home, and the wife to rejoice in the operation of her hands, and it is an adage not I think without some truth, that cleanliness is almost next to godliness.

3-: From A remarkable Epitaph, published in The Lady’s Magazine; Or, Entertaining Companion for the Fair Sex, appropriated solely to their Use and Amusement (London: Printed for G. Robinson) of May 1778:

On the morning of the 31^st of January, 1776, a female of exquisite beauty, and great merit, departed this life, after an irksome illness of five months, which she bore with uncommon patience and fortitude. Her gentleness of disposition, sweetness of temper, and goodness of heart were all conspicuous in her honest, complaisant countenance, and could only be equalled by her constancy and fidelity, and these last exceed all description. For cleanliness through her whole life, (a virtue next to godliness) she was not to be excelled. She was always remarkably neat and decent in herself, therefore was ever averse to seeing any person in rags. […]
[…]
The foregoing epitaph was written by the late Captain Knox on his favourite bitch Phillis.

4-: From Minutes of Several Conversations, between the Rev. John Wesley, A. M. and the Preachers in Connection with him. Containing the Form of Discipline established among the Preachers and People in the Methodist Societies (London: Printed for G. Whitfield, 1779):

§ V. The peculiar Business of a Superintendent.
Q. 6. What is the business of a Superintendent?
A. To see that the other Preachers in his Circuit behave well, and want nothing. […]
[…]
The following Advices are recommended to all the Superintendents.
[…]
Every where recommend decency and cleanliness. Cleanliness is next to Godliness.

5-: From The Miscellaneous Companions: Vol. I. Being a Short Tour of Observation and Sentiment, through a Part of South Wales (Bath: Printed for the author, by R. Cruttwell, 1786), by William Matthews:

About half a mile out of town, a turnpike crossed the road, and an elderly woman, by degrees, opened the gate: she proved, however, to be a woman of observation and reason, at least of reasoning. […]
If you go forward, said she, let me advise you to take off that skin from before you, and tie round your head and neck! It was in vain that I urged my large great coat and well-covered hat, as proofs of my being sufficiently guarded against wind and weather: you had better, said she, take my advice—for we Welch always take care to guard against cold at our ears.
This she had evidently taken care to do; for it seemed pretty certain, that the covering of her own head, which was composed of old handkerchiefs and flannel, had not been taken off to admit the injury of any air, or washing of her skin, for many a gloomy day and many a sleepy night:—But such a description is not to be dwelt on by way of reproach, any more than for the sake of its delicacy.
Our minds, on such occasions, are involuntarily transported into the Southern ocean, to make comparisons of our new discoveries, with old ones among the Hottentots—then we recur to our old maxim at home, that next to godliness is cleanliness—but till we can be better satisfied, from observation, that benevolence, content, and enjoyment, are not as sweetly felt, under the accumulated dirt of the poor people before us, as among our washings, bathings, and elegance, we may only be smiled at for drawing any great balance in our own favour! But while I would exchange a thought with the moralist, and satisfy myself en passant, with new proofs of the commonwealth of human happiness; I would not lay a stumbling-block in the way of our wives and daughters, and thereby lessen their zeal to excel in cleanliness and every rational species of œconomy.

6-: From Sermon XXXIV. on Matt. XXV. 36., published in The Arminian Magazine […]. Consisting chiefly of Extracts and Original Treatises on Universal Redemption [note 2] (London: Printed by J. Paramore) of October 1786:

Together with the more important lessons, which you endeavour to teach all the poor whom you visit, it would be a deed of charity to teach them two things more, which they are generally little acquainted with: Industry and Cleanliness. It was said by a pious man, “Cleanliness is next to Godliness.” Indeed the want of it is a scandal to all Religion; causing the way of truth to be evil spoken of. And without Industry we are neither fit for this world, nor for the world to come. With regard to both, Whatsoever thy hand findeth to do, do it with thy might.

Notes:
1 John Wesley’s sermon On Dress has been dated to 1778, also to 1788. I have, however, been unable to ascertain its date.
2 The Arminian Magazine was a Methodist magazine founded by Joh Wesley in 1778.