Unfortunately, I don't think there's many options in Uyuni for accommodation.
I slept in the same place Peter mentions, and I was honestly anxious when it began to get colder and colder outside. The 'common area' was fine though, the tour guides (a really nice couple) gave us some sleeping bags and there were also blankets in the room. It might be because there were 6 of us in the room, or perhaps we were all just very excited about the geysers we were going to visit the next morning (it felt very mystical), but we weren't cold at all. Just in case, we went to sleep with our clothes on (including wool hat that covered the ears - a great accessory to have!), and it was great.
It's worth mentioning that that same place (I can't remember the name, but I think most tours do a night there) is 200 meters away from one of the most amazing things I've seen in my life. When I went, in 2008 or so, there was a very small museum. If you are there, don't miss it. Right behind it are the chulpas, that are tombs constructed inside what used to be corals (from when Uyuni was a prehistoric lake). There was only one person living there and taking care of them, and he showed us the whole place, explaining the history and the importance of the place. It was unbelievable.
There is also another hotel we visited, called Palacio de Sal (palace of salt). We didn't sleep there, but we talked to people from other tours that had, and they said they had an extremely cold night. This might have changed though.
Places like Uyuni might not have (not even remotely) comfortable options. At least not like you might be used to in other places. But you will be sleeping in the middle of one of the most amazing natural wonders, close to the people who actually spend their whole lives there. And it honestly feels really good to feel happy with what you will find. And that is a decently warm bed, excellent food, great company, and adventure.