The obvious way is to load up JDBC support from Clojure Contrib and write some function to translate a map/struct to a table. One drawback of this is that it isn't very flexible; changes to your structure will require DDL changes. This implies either writing DDL generation (tough) or hand-coding migrations (boring).
What alternatives exist? Answers must be ACID, ruling out serializing to a file, etc.
Clj-record is an implementation of active record in clojure that may be of interest to you.
Using CouchDB's Java-client lib and clojure.contrib.json.read/write works reasonably well for me. CouchDB's consistency guarantees may not be strong enough for your purposes, though.
One option for persisting maps in Clojure that still uses a relation database is to store the map data in an opaque blob. If you need the ability to search for records you can store indexes in separate tables. For example you can read how FriendFeed is storing schemaless data on top of MySQL - http://bret.appspot.com/entry/how-friendfeed-uses-mysql
Another option is to use the Entity-Attribute-Value model (EAV) for storing data in a database. You can read more about EAV on Wikipedia (I'd post a link but I'm a new user and can only post one link).
Yet another option is to use BerkeleyDB for Java - it's a native Java solution providing ACID and record level locking. (Same problem with posting a link).
You could try one of the Java-based graph databases, such as Neo4J. It might be easy to code up a hashmap interface to make it reasonably transparent.