First, let's examine what the books tell us.
In Chamber of Secrets chapter 9, Argus Filch describes his cat as “all stiff and frozen” when she is Petrified.
In chapter 10, Harry meets the Petrified Colin Creevey in the hospital wing.
Harry's stomach gave a horrible lurch. Slowly and carefully, he raised himself a few inches so he could look at the statue on the bed. A ray of moonlight lay accross its staring face.
It was Colin Creevey. He eyes were wide and his hands were stuck up in front of him, holding his camera.
[…] Then Dumbledore leaned forward and prised the camera out of Colin's rigid grip.
In chapter 11, Harry finds two victims Petrified:
Justin Finch-Fletchey was lying on the floor, rigid and cold, a look of shock frozen on his face, his eyes staring blankly at the ceiling. And that wasn't all. Next to him was another figure, the strangest sight Harry had ever seen.
It was Nearly Headless Nick, no longer pearly-white and transparent, but black and smoky, floating immobile and horizontal, six inches off the floor.
In chapter 14, when Hermione and Penelope are petrified
Hermione lay utterly still, her eyes open and glassy.
In chapter 16, we learn a bit more when Harry and Ron visit the Petrified Hermione in the hospital wing.
Madam Pomfrey let them in, but reluctantly.
‘There's just no point talking to a Petrified person,’, she said, and they had to admit she was right when they'd taken their seat next to Hermione. It was plain that Hermione didn't have the faintest inkling that she had visitors, and that they might just as well tell her bedside cabinet not to worry for all good it would do.
[…] Hermione's hand was clamped so tightly around the paper that Harry was sure he was going to tear it.
This suggests that Hermione wasn't aware of her surroundings, though I'm not sure how Harry would be able to tell this about a person who's magically paralyzed. This appears different from the paralysis spell (Petrificius Totalus): when Malfoy casts that on Harry in Prince chapter 7, Harry is aware of his surroundings. (Hermione casts the same spell on Neville in Stone chapter 16, but the situation is less clear.)
Based on the meeting with Hermione alone, I could imagine that the Basilisk's Petrification effect only paralyzes you on your entire body just like this spell, but Madam Pomfrey magically makes the victims unconscious for it would be very inconvenient to them to be paralyzed and conscious for months. However, the description of Justin's attack makes it clear that Justin's body was cold, so the basilisk's stare can't be just an ordinary paralysis effect, there is a physical change.
In summary, a Petrified person becomes paralyzed on his whole body, including his head, his body becomes rigid and cold, and the person becomes unconscious.