Do it with databases.
I suggest creating a categories table with the following fields:
id, title, description, parent_id
the parent_id field will allow you to create infinite sub categories. you can set 0 as a default parent_id to indicate that it is a top-level category.
then in your classified listings table, you'll have a field named "category_id" which will associate the listing with a category. but you may wish to consider using a second relations table (classifieds_to_category) if you want to map a listing to multiple categories.
As far as knowing where to start: that depends on your skill of PHP/databases. Start of by creating the database tables, inserting some data (or just some dummy data), and then coding the front-end to display your listings and categories. Then move onto creating the registration and later an admin interface so you can manage listings easily.
-sridhar
