Cool! You are at the start of a great adventure!
First, forget client-side. It's not designed for this sort of stuff.
CGI is *server* side. It's a convention for passing parameters to a server-side script, not a language in itself. For example, Perl uses CGI and Perl programs (and others) are sometimes called "CGI scripts" leading to some confusion.
To declare my own interest, I write Perl that accesses MySQL. This is quite standard, though a lot of people use PHP and it is generally considered "easier to learn". "Best" and "easiest" are highly subjective terms. From a functional point of view, what you're planning to do is probably quite straightforward. Take form input, put it in a database. Take form input, query the database and display the results. It's not rocket science and an awful lot easier IMHO than say event-driven GUI stuff.
Also you refer to msql but MySQL is more commonly used, free(ish) and more powerful so it's a better one to go for. Though from a programming point of view they're extremely similar.
As you're already a programmer I'd say learn Perl and go that route. If you can do C, for instance, then Perl is a doddle. And of course there are lots of useful things you can do with Perl away from the web too.
For a cheap and easy intro to Perl/CGI, get Perl and CGI for the WWW by Elizabeth Castro. This doesn't cover databases but will get you started writing Perl scripts without bogging you down in heavy theory or irrelevant and silly topics.
Check out www.perl.com
Also "Programming the Perl DBI" by Descartes/Bunce is *the* book on Perl database access. MySQL & msql by Yarger/Reese/King is also useful but not essential.
I'm not claiming some ultimate truth here. There are many ways of approaching this. But this is the route that worked for me coming from the same place as you.
Given time, learn them all! (Why not?)