She probably entered the Ministry via the Floo Network
It is true that in Deathly Hallows the Trio entered the Ministry via toilets.
“Morning, Reg!” called another wizard in navy blue robes as he let
himself into a cubicle by inserting his golden token into a slot in
the door. “Blooming pain in the bum, this, eh? Forcing us all to get
to work this way! Who are they expecting to turn up, Harry Potter?”
—Harry Potter and the Deathly Hallows
However, this language used to describe this strongly suggests that this is not the normal way for Ministry employees to get to work ("this way").
Before the Ministry was taken over by Voldemort, people emerged from the same fireplaces (though perhaps not by flushing themselves down toilets).
The walls on each side were panelled in shiny dark wood and had many
gilded fireplaces set into them. Every few seconds a witch or wizard
would emerge from one of the left-hand fireplaces with a soft whoosh.
—Harry Potter and the Order of the Phoenix
Indeed, the fireplaces filled with green flames when active:
The Atrium was full of people; the floor was reflecting the emerald
green flames that had burst into life in all the fireplaces along one
wall; and streams of witches and wizards were emerging from them. As
Dumbledore pulled him back to his feet, Harry saw the tiny gold
statues of the house-elf and the goblin, leading a stunned-looking
Cornelius Fudge forward.
—Harry Potter and the Order of the Phoenix
Emerald flames are, of course, a sign of Floo Powder usage:
“Not now, Arthur,” said Mrs. Weasley. “Floo powder’s a lot quicker,
dear, but goodness me, if you’ve never used it before —”
“He’ll be
all right, Mum,” said Fred. “Harry, watch us first.”
He took a pinch
of glittering powder out of the flowerpot, stepped up to the fire, and
threw the powder into the flames. With a roar, the fire turned
emerald green and rose higher than Fred, who stepped right into it,
shouted, “Diagon Alley!” and vanished.
—Harry Potter and the Chamber of Secrets
And of course, most definitively:
“Dad always told us most Ministry people use the Floo Network to get
to work,” Ron said. “That’s why we haven’t seen Umbridge, she’d never
walk, she’d think she’s too important.”
—Harry Potter and The Deathly Hallows
Before the additional security measures implemented when Voldemort took over, it would be relatively easy for Voldemort, if he had access to a home connected to the Floo Network (as, for example, Malfoy Manor must surely have been) to simply let Nagini slither into the fireplace and send her away.
She could use the lifts
It's true that we are not shown any other way but the lifts of reaching Level 9, home of the Department of Mysteries. It is also the case that the lifts are operated by buttons:
He pressed the nearest 'down' button and a lift clattered into sight
almost immediately, the golden grilles slid apart with a great,
echoing clanking and they dashed inside. Harry stabbed the number
nine button; the grilles closed with a bang and the lift began to
descend, jangling and rattling.
—Harry Potter and the Order of the Phoenix
However, two things work in her favor. First, Voldemort was possessing her at the time (at least according to Snape, who is knowledgeable in matters of the Dark Arts):
'You seem to have visited the snake's mind because that was where the
Dark Lord was at that particular moment,' snarled Snape. 'He was
possessing the snake at the time and so you dreamed you were inside
it, too.'
—Harry Potter and the Order of the Phoenix
Of course, as Lord Voldemort's final Horcrux, Nagini has a stronger-than-normal connection to him to begin with:
“As we know, he failed. After an interval of some years, however, he
used Nagini to kill an old Muggle man, and it might then have occurred
to him to turn her into his last Horcrux. She underlines the Slytherin
connection, which enhances Lord Voldemort’s mystique; I think he is
perhaps as fond of her as he can be of anything; he certainly likes
to keep her close, and he seems to have an unusual amount of control
over her, even for a Parselmouth.”
—Harry Potter and the Half-Blood Prince
Voldemort could certainly have helped provide her with the mental powers needed to operate the lift, along with the knowledge needed to do so.
As for the physical ability, I refer you to this video of a giant snake opening a door.
If an ordinary snake (possibly trained by a mere Muggle) can stand on its tail and open a door at the same time, a snake possessed by Voldemort probably can stand on its tail and hit buttons with its head. It's not very dignified, but it's probably what happened.
Voldemort was well-informed, and may have concealed her.
There probably was a Ministry guard on duty that night.
Harry noted the absence of a security guard was a bad sign when he went to the Ministry:
Harry felt sure there ought to be a security person there, sure their
absence was an ominous sign, and his feeling of foreboding increased
as they passed through the golden gates to the lifts.
—Harry Potter and the Order of the Phoenix
As it turns out, there is indeed a wizard who takes the night watch:
Podmore was arrested by Ministry of Magic watchwizard Eric Munch, who found him attempting to force his way through a top-security door at
one o'clock in the morning.
—Harry Potter and the Order of the Phoenix
To this, all I can say is that Nagini was stealthy, and probably waited until the watchwizard was elsewhere. Alternately, it is highly probable that Voldemort put a Disillusionment Charm on her, to conceal her presence. In that case, all he would need to know would be when the watchwizard's shift changed, or when they would not be at their desk: information easily obtained by Lucius Malfoy from his Ministry contacts.
