I'd like to do a simple online address book, searchable, etc. I'm a beginner and have established a connection but not sure what next.

Depending on the level of complexity you want I would say that you probably want one or two tables.

If it is literally just the messages you want to store then a messages table, but if you want to use their contact info elsewhere then you should probably consider using 2 tables:
A table to hold their personal details (name, email address, ways to contact them ICQ, MSN etc) and another for the message (text of the message, keywords, date etc)

Next you would build a form that lets your user enter their name, email address and write their message. Give the form elements the same names as those in the database so that when you use the built in dmx server behaviour INSERT RECORD it will automatically match the webpage elements to the database fields.
Put a submit button on the form and that's about it.

Let me know if you want any help with db structure or any more help with the page.

HTH

Simon