What MySQL storage engine should I choose?
My recommendations are to start as follows:


Go for the latest version of the MySQL Server that you can get, there have been some pretty impressive work done on 5.6 although the production ready version is 5.5
Go for InnoDB - comes as the default for the higher MySQL versions
Configure InnoDB as follows:


file_per_table - creates an data file for each table instead of putting all tables in a single data files
innodb_buffer_pool_size - 80% of available RAM (if a dedicated machine) so that as much of your database is in memory

Table column characteristics:


use the smallest column size needed for the data
use numeric foreign keys
index the columns used in the searches, and setup the indexes to cover the most common searches, for example if you search on columns 4, then 6 alot create a multi-column index with column 4 first followed by 6 



Remember these are just starting points you can fine tune specifics as you move along, but before you fine tune, measure tune then measure again