best way to design mysql database table so that columns can be searched quickly sn

[andreea gosh]

Hi everyone
Can someone please explain to me how MySQL searches through a database of multiple tables?
The reason for the question is that I am trying to determine the best way to design A database that would allow me to index many searchable columns within the tables.
It might be best if I show you what I mean;
I have a user entity that has many categories like;
Gender
countryLocation
LocationPostCode
Main language spoken
Country visited
Available date
Smoker
Driver ETC ETC
I expect to have millions of registered USERS s and will ALLOW members to search the database by one or many of the above categories..
QUESTION
Is it best therefore to keep all these columns in one table and then index each of them?. I however read somewhere that indexing several columns on a table affects performance .
Alternatively, should I make separate tables for EACH of these main items and then just have the user_ id indexed in each of these tables. (i.e MySQL would then make a separate FETCH to each of these table to fetch all the Id in each table).
I understand however that JOIN are a costly operation for MySQL to perform and that its quicker for it to work from one table.
I would be very grateful if someone could explain the right approach and also explain how the engine conducts the search. I seem to be getting contrary information from many different sources.
Warm regards

Andreea