The earliest I can see is from 1829:
The Casket, Or, Flowers of Literature, Wit & Sentiment
Volume 4. Anonymous. Printed and Published By Atkinson & Alexander.
"To rove at will through ether's wide domain,
And there commune with nature and with God."
But the expression seems to have been popular by the 1830s, appearing in the American Annals of Education and Instruction, in a poem by Edgar Allan Poe and in "The Excursion" by Wordsworth (1836). So it may well be older.
Wordsworth's poem says,
".......................................For the man
Who, in this spirit communes with the Forms
Of Nature, who with understanding heart...
(It's the index that refers to this passage as "communes with nature.")
Here it is in 1854, in The Churchman's Monthly Magazine - Volume 1 - P.113
He sat down on a rock and said, — "Here I will commune with nature."
I replied, "And I will go on a little further and commune with God!"
"Stay," he cried, "I would go with you."
"But you cannot see him," I said. "I see him in the mountain, and the glacier, and the flower. I hear him in the torrent and the still small voice of the rills and waterfalls."