How to optimise dynamic pages?

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

I would like to make my web application search engine friendly.

The web application itself is a form of domain specific search engine
/ generated catalog. It scans webpages of travel agencies and collect
prices and other information of last minute travel offers and puts
them into a single catalog. The web application is in danish and
updates every 4th hour.

The interface has a selectable sort order, type, pagination and
filters on  country, airport and departure date. The is a default
selection when the application is hit on its index showing travels
that include hotel, going to any country with departure within 2
weeks, sorted by date.

Now: I would like to optimise for keywords such as afbudsrejse (last
minute travel), rejse (travel) etc. Possibly specific phrases like
afbudsrejse spanien (last minute travel spain) which should lead to
the catalog filtered with country Spain.

I can generate title tag and meta data depending on the search
criteria. It is also possible to change the url structure into
something like .../afbudsrejser/spanien?index=50&... so it looks more
like a static page.

Can anyone give some advice as to what efforts (metadata, title, url,
doorway pages) will be fruitful? I have heard somewhere that some
search engines do not index dynamic pages unless they have paid for
inclusion. Is this true? And if so can one bypass that by removing any
signs that the page is dynamic (e.g. the .jsp extension).

Currently I have submitted the site url to Google and made a link from
my blog but it is not showing up. If I search for the title of the
application "Katalog over Danske afbudsrejser" my blog (linking to the
application) shows up as first result but the application itself does
not appear to indexed. (Submitted little over a week ago - maybe I am
just impatient.)

The application:

Christian Hvid

Site Timeline