Does the new passport also come with visas stamped?
Just out of curiosity, how did you expect that to work?
A passport is issued by your own country and the visa are not, those are issued by other countries.
So how would your country organize that for you and why should they?
If not, then do I travel with the old (damaged) passport with valid visas and a new re-issued empty passport (just for stamping by the immigration officers when I travel) ? Or how does it work exactly?
Yes, that is exactly how that works.
Your old passport gets invalidated but you may need to explicitly request that the invalidated passport is returned to you, preferably with the pages containing valid visa undamaged, as the typical procedures to invalidate passports seems to be to punch a couple of very big holes in them. (See for instance What should I do with my expired passport? )
Usually the visa in an old passport will remain valid. Specifics are dependent on the countries that issue the visa and your own new passport.
See for instance specific Q&A's already present here:
What happens to visas that last longer than a passport? ,
Can I travel to Canada with valid visa on old/expired passport? ,
Valid Vietnam tourist visa in old passport,
Valid Indian visa in an expired passport etc. etc.