The simplest way to connect to an external relational database (as opposed to an in memory database like berkeley db) is via JDBC. You should get familiar with JDBC before you progress on to any other storage methods. For most projects you will be fine using either mysql or postgresql. Don't worry about deciding on one over the other, for smaller projects the differences are not that relevant. As long as you are using jdbc you will be ble to switch between the two later if you really need to.
To get started I would download mysql and follow the jdbc tutorial on the sun site http://java.sun.com/docs/books/tutorial/jdbc/index.html ).
At a later date you may decide you need to use an object-relational-mapping tool, like hibernate, but I would not worry about that now either, just get familiar with jdbc and either mysql or postgresql.