1)
Why did they believe him?
1.
Radak: People from the boat were in the city, and testified that they cast him to the sea and the entire episode. Therefore, they believed his prophecy and repented totally.
2.
Malbim: This was a Chidush. They did not request a sign. They immediately began Tefilah, wearing sackcloth, fasting and humility. They were not aroused to Teshuvah, for they did not realize that they sin, for Yonah did not inform them 1 .
1
Why did they think that Hashem will destroy them, if not that they sinned? They returned "the theft in their hands" (8) - did they not realize that this is a sin? (PF)