I read this around 10 years ago and it was an old book I bought from the school library. It was maybe around 200-300 pages and not a large book. I read it when I was young, so I don't remember everything. What I do know is:
- The traveler was a man.
- The cat was large (think panther), a female, and maybe colorful.
- The cat could also speak telepathically to the man, however, the man could not hear that the cat was female.
- Further in in the book, the cat realizes that she's pregnant, and after a while, so does the man (which makes him realize it's a female).
- On the planet, quite often, a sand storm rages on, so they have to hide in holes.
- The cat was either banished from her home town or she ran away.
Sadly, I don't remember anything more about the plot.