It is clear that Jesus was crucified naked, both from this passage and from comments in other passages in the New Testament. The original Greek in this passage is as follows:
Οἱ οὖν στρατιῶται ὅτε ἐσταύρωσαν τὸν Ἰησοῦν ἔλαβον τὰ ἱμάτια αὐτοῦ καὶ ἐποίησαν τέσσαρα μέρη ἑκάστῳ στρατιώτῃ μέρος καὶ τὸν χιτῶνα ἦν δὲ ὁ χιτὼν ἄρραφος, ἐκ τῶν ἄνωθεν ὑφαντὸς δι᾽ ὅλου
Let's break the verse down into parts:
Οἱ οὖν στρατιῶται ὅτε ἐσταύρωσαν τὸν Ἰησοῦν
Then the soldiers when they crucified Jesus
ἔλαβον τὰ ἱμάτια αὐτοῦ
took the garments of him
καὶ ἐποίησαν τέσσαρα μέρη
and made four parts
ἑκάστῳ στρατιώτῃ μέρος
to each soldier a part
καὶ τὸν χιτῶνα
and the tunic.
ἦν δὲ ὁ χιτὼν ἄρραφος,
Was now the tunic seamless,
ἐκ τῶν ἄνωθεν ὑφαντὸς δι᾽ ὅλου
from the top woven throughout all
It is clear here that there is no mention of an undergarment. Others have mentioned it was common to wear a loincloth under their outer garments, and have mentioned Jeremiah 13 in support of this, using a translation that translates the Hebrew word אֵזוֹר as "loincloth." This is a mistranslation of the word, which really means a girdle, belt, or a sash, and not an undergarment.
Lastly, it is clear he was naked on the cross because of the shame. Hebrews 12:2 says:
Looking unto Jesus the author and finisher of our faith; who for the joy that was set before him endured the cross, despising the shame, and is set down at the right hand of the throne of God.
What might be difficult for modern Western readers to understand is the context for the shame of nudity in the Bible, as well as the use of euphemisms in the Hebrew Old Testament. Going back to Noah, it says he was uncovered in his tent, and that Ham saw his father's nakedness. While it's not entirely clear what was going on in the passage, the term "uncovering nakedness" was used in Hebrew as a euphemism for some form of sexual compromise, so it wasn't simply that Noah was naked and Ham happened to see it. There are numerous other passages throughout the Bible where people were completely naked in public without being condemned.
What was shameful about nakedness then? Isaiah traveled around and preached naked (Isaiah 20), and King Saul (I Samuel 19:24) and the prophet Micah (Micah 1:8) prophesied naked, after all. It all comes down to whether this was voluntary or not. Every passage in the Bible that talks about the shame associated with nakedness is talking about it being forced on a person. In Isaiah, the prophet willingly stripped naked as an object lesson to warn others to repent. If they did not, they would end up as naked as he was, he warned, but it would be shameful because their clothing would be forcibly taken away from them, which happened regularly when one was taken as a slave.
Yes, Jewish people saw nakedness as shameful, but this shame was contextual. It was not the human body seen as shameful in and of itself, but the shame of having one's clothing, the symbol of their status, forcefully taken from them and being put on display. Jesus, though, going back to the passage in Hebrews, rose above that. Paul, in I Corinthians 15, referred to Jesus Christ as a "second Adam." In Genesis 2, there is a passage that reads: "And they were both naked, the man and his wife, and were not ashamed." Just as the first Adam was not ashamed before the fall, so Jesus, as the second Adam, was not ashamed to be put on display, taking the punishment of the world on his shoulders.