Most of the cardinals don't live (most of the time) in the neighborhood of the Vatican. So, probably, once the Church as a whole got over the shock, they'd convene the college of cardinals in some appropriate place and elect a new Pope.
Now if (as Caleb hypothesizes in his comment) the college of cardinals were largely or entirely wiped out as well, then we'd probably need to appoint new cardinals. Typically, of course, this is reserved for the Pope; but in this case we'd obviously have to work in a new way. One might consider the Code of Canon Law:
Can. [i.e. Canon] 335. When the Roman See is vacant or entirely impeded, nothing is to be altered in the governance of the universal Church; the special laws issued for these circumstances, however, are to be observed.
Can. 336 The college of bishops, whose head is the Supreme Pontiff and whose members are bishops by virtue of sacramental consecration and hierarchical communion with the head and members of the college and in which the apostolic body continues, together with its head and never without this head, is also the subject of supreme and full power offer [sic, i.e. "over"] the universal Church.
Now it's arguable whether this is enough to allow the college of bishops to appoint cardinals if the see is vacant and there are none; but I'm guessing that it probably is.
It's highly unlikely that all the cardinals would be in Rome at once; I'm not sure that they always are even for a conclave. If there are any cardinals at all left, the college of bishops might only have to indicate that the restriction on voting for cardinals over the age of 80 has been lifted; then a new conclave can be called. If there are no cardinals left at all, then as I said I think you could use Canons 335 and 336, or something similar, to argue that the college of bishops must in these extraordinary circumstances receive the ability sede vacante to appoint new cardinals. From there the process would proceed as usual.
A council of bishops might be needed to determine where the Holy See would be, but the new Pope would be able to appoint new heads of the various congregations and the other structures of the Holy See. It would certainly be a great blow to the Church, but the Church has a widely dispersed power structure and would be able to pick itself up fairly easily, I think.
One other note: I'm not familiar with the governance of the Eastern Catholic Churches, nor with the canon law regarding them, so I've left them out; but presumably their patriarchs would not have been affected by a catastrophe such as you imagine. Unless you want to specify that there were quite a number of simultaneous catastrophes in different places.