First story to describe humans colonizing another planet?

I think that Last and First Men, by Olaf Stapledon qualifies, published in 1930.

It describes a couple of billion years of human evolution, in different waves of men. The 8th and 9th waves describe genetically altering humans to live on Neptune, after similar attempts on Venus failed:

Venus:

Fifth Men. (Chapters 11–12) An artificial human species designed by the brains. "On the average they were more than twice as tall as the First Men, and much taller than the Second Men... the delicate sixth finger had been induced to divide its tip into two Lilliputian fingers and a corresponding thumb. The contours of the limbs were sharply visible, for the body bore no hair, save for a close, thick skull-cap which, in the original stock, was of ruddy brown. The well-marked eyebrows, when drawn down, shaded the sensitive eyes from the sun." After clashing with and finally eliminating the Fourth Men, they develop a technology greater than Earth had ever known before. When Earth ceases to be habitable, they terraform Venus, committing genocide on its marine native race which tries to resist them – but do not cope well after the move.

Neptune:

Eighth Men. "These long-headed and substantial folk were designed to be strictly pedestrian, physically and mentally." When Venus becomes uninhabitable, about to be destroyed along with the entire inner solar system, they design the Ninth Men, who will live on Neptune.

Ninth Men. (Chapter 14) "Inevitably it was a dwarf type, limited in size by the necessity of resisting an excessive gravitation... too delicately organized to withstand the ferocity of natural forces on Neptune... civilization crumbled into savagery." After the Ninth Men's civilization collapses, the Ninth Men themselves devolve into various animal species.

Either The War of the Worlds by H.G. Wells (1897) or "Crashing Suns" by Edmond "World Wrecker" Hamilton (1928)

Until an earlier example is found.

I was going to post a Stanley G. Weinbaum story as earlier than Last and First Men in JohnP's answer, then noticed that Last and First Men is dated to 1930, not 1939. But I expect that mentions of colonies on other planets should date back to the first pulp science fiction magazine, Amazing Stories in March, 1926, or even earlier.

The first plausible moon colony or base with domes to contain an Earth-like atmosphere was probably in Brigands of the Moon by Ray Cummings, Astounding Stories of Super Science, March, April, May, and June 1930.

http://www.technovelgy.com/ct/content.asp?Bnum=9561

http://www.isfdb.org/cgi-bin/title.cgi?206872

Edmond "World Wrecker" Hamilton's stories of the Interstellar Patrol were preceded by a story of the Interplanetary Patrol where humans had colonized all the planets of the solar system, "Crashing Suns", Weird Tales August 1928, and September 1928. Since the first issue of Weird Tales was in March, 1923, the first story of human colonies on other worlds could have been published in 1923.

http://www.isfdb.org/cgi-bin/title.cgi?781093

And no doubt earlier examples will be found by those more familiar with early science fiction.

In The War of the Worlds by H.G. Wells, it is believed that the outer planets are older and the inner planets are younger, and that the outer planets will "die" and become lifeless before the younger ones. Thus the Martians invaded Earth because Mars was dying.

In Chapter Ten: The Epilogue, the narrator says:

Lessing has advanced excellent reasons for supposing that the Martians have actually succeeded in effecting a landing on the planet Venus. Seven months ago now, Venus and Mars were in alignment with the sun; that is to say, Mars was in opposition from the point of view of an observer on Venus. Subsequently a peculiar luminous and sinuous marking appeared on the unillumined half of the inner planet, and almost simultaneously a faint dark mark of a similar sinuous character was detected upon a photograph of the Martian disk. One needs to see the drawings of these appearances in order to appreciate fully their remarkable resemblance in character.

At any rate, whether we expect another invasion or not, our views of the human future must be greatly modified by these events. We have learned now that we cannot regard this planet as being fenced in and a secure abiding place for Man; we can never anticipate the unseen good or evil that may come upon us suddenly out of space. It may be that in the larger design of the universe this invasion from Mars is not without its ultimate benefit for men; it has robbed us of that serene confidence in the future which is the most fruitful source of decadence, the gifts to human science it has brought are enormous, and it has done much to promote the conception of the commonweal of mankind. It may be that across the immensity of space the Martians have watched the fate of these pioneers of theirs and learned their lesson, and that on the planet Venus they have found a securer settlement. Be that as it may, for many years yet there will certainly be no relaxation of the eager scrutiny of the Martian disk, and those fiery darts of the sky, the shooting stars, will bring with them as they fall an unavoidable apprehension to all the sons of men.

The broadening of men's views that has resulted can scarcely be exaggerated. Before the cylinder fell there was a general persuasion that through all the deep of space no life existed beyond the petty surface of our minute sphere. Now we see further. If the Martians can reach Venus, there is no reason to suppose that the thing is impossible for men, and when the slow cooling of the sun makes this earth uninhabitable, as at last it must do, it may be that the thread of life that has begun here will have streamed out and caught our sister planet within its toils.

Dim and wonderful is the vision I have conjured up in my mind of life spreading slowly from this little seed bed of the solar system throughout the inanimate vastness of sidereal space. But that is a remote dream. It may be, on the other hand, that the destruction of the Martians is only a reprieve. To them, and not to us, perhaps, is the future ordained.

I don't know if a character's speculations about possible future colonization of Venus counts as a story about humans colonizing another planet. If it does, The War of the Worlds (1897) might be the first, if not "Crashing Suns" (1928) might be the first. Until someone finds an earlier example.

Written in the 2nd century AD, Lucian's A True Story has the King of the Moon and the King of the Sun fighting a battle over the colonisation of Venus.

A translation is available here:

We asked who the enemy were, and what the quarrel was about. "Phaethon," said he, "the king of the inhabitants of the sun--for it is inhabited, you know, as well as the moon--has been at war with us for a long time now. It began in this way. Once upon a time I gathered together the poorest people in my kingdom and undertook to plant a colony on the Morning Star, which was empty and uninhabited. Phaethon out of jealousy thwarted the colonisation, meeting us half-way at the head of his Ant Dragoons. At that time we were beaten, for we were not a match for them in strength, and we retreated: now, however, I desire to make war again and plant the colony."

Discounting the entry for The War of the Worlds since it doesn't actually describe the act of colonization, I nominate The Struggle for Empire (1900) by Robert William Cole.

The planet Iosia, in an unnamed star system (that is not Sol or Sirius) is colonized first by Earth-humanity (in the name of the Anglo-Saxon Empire) and then in a hostile counter-colonization by the people of Kairet (a planet of Sirius):

For a long time past, a band of adventurers had been colonizing a planet called Iosia, which was situated far beyond the confines of the Sirian System. This planet was particularly rich in mineral wealth and other natural products, hence its possession was considered by the Colonial Bureau to be a most valuable acquisition. But shortly after the first party of Anglo-Saxons had landed there, its existence became known to the people of Kairet, the ruling planet of the Sirian System, and they much coveted the enormous resources which it was rumoured to possess. Small parties of colonists were sent out and took possession of tracts of land that were far remote from those occupied by the Anglo-Saxons; but this was not at first noticed by the latter. ...

[...]

... At last, however, by some awkwardness of fate both nations hit upon the same site for founding a city. It was a spot that was eminently fitted, both by climate and surroundings, for such a purpose. Both parties were equally determined not to yield, so amidst much quarrelling they both began to make preparations for building on the same spot. An open rupture could not now be much longer delayed.

_{The Struggle for Empire, Chapter III: The First Note of War}

So we have not just operations to extract minerals, which might not be considered an actual colony, but the occupation of land and the construction of cities, which definitely counts as the establishment of a true extra-solar colony.