Sounds like you want something AJAX-y, which means this isn't strictly a Perl question. Check out script.aculo.us for that route.

The more portable non-Javascript thing to do though would be to just have a form that submits to another CGI (or the same one with an extra parameter) which makes it generate a new page with the new table.