thread table - thousands of entries (in fact this is the thread table from VBulletin)
user table - thousands of entries on a big forum (this is the user table from VBulletin)
icon table - less than 50 items; this is the "icon" table from Vbulletin.
The joins will be made on primary keys of type int.
I am not sure about the storage type, but I think it is INNODB. I have to check about this on the server, if you think that it is important.
First of all, just by answering your question I got a different perspective. Tables 1, 2 and 3 can all be HUGE tables. That being the case it might be better to avoid the join completely because it can use insane amounts of RAM when the forum grows.
Currently, I have a join between "story" table and "thread" table. I don't know if I should keep this join. Hmm.... what to do ? If I will kill this join then I will easily get 60-70 queries per page.
The join is the better option because it uses less overhead. Interesting you are ussing inno, is there a reason? do you ever backup your datatbase? did you purchase inno hotcopy?
run the query through explain, see what it looks like.