You may use only one variable (or any other categorization) as your stratum and do the random sampling for each category of your chosen stratum. Ensure that the sample size is proportionally distributed to each category of your stratum. As long as you do random sampling in each category of the chosen stratum, the categories of the other variables will also be well represented in your sample. 

Girija -

The optimum sample allocation for a stratified random sample depends upon the strata standard deviations.  However, if you are interested in estimating a total, mean, or proportion (latter for yes/no data, others for continuous data) for each stratum, then you really have a series of simple random samples.  You need to estimate the minimum sample size you need, either for a stratified random sample, or for each stratum, if you want to publish estimates for them, and all this, for each variable of interest, and pick the maximum sample size needed to yield the minimum standard errors required for all of your necessary-to-estimate-well variables.  Note that yes/no data are not handled with the same "formulas" as continuous data, and I have noticed that apparently most online calculators for sample sizes assume yes/no data, simple random sampling, no finite population correction factor, and the worst case (p=q=0.5) rather than look at standard deviations more exactly.  Many people seem to use such calculators incorrectly.  They are quite limited in applicability.

There are a number of good references, such as Cochran, W.G(1977), Sampling Techniques, 3rd ed., John Wiley & Sons. Cochran has a chapter on sample size needs determination for simple random sampling, covering both continuous and yes/no data, for both finite and infinite populations, and then follows with chapters on stratified random sampling and other design information, with notes in those chapters on sample size requirements. 

Also, I see that https://onlinecourses.science.psu.edu/stat506/node/26 references Thompson, another very good book.  There are links at the bottom of that documemt which will take you to various information in other URLs that should be helpful for you.

Cheers - Jim

PS - If you have auxiliary/regressor data on the population beyond what you need to stratify, you can do even better, but that is more advanced.  I have references for a number of books, re continuous data, if you are interested.  

PSS -  I don't know "Krecie and Morgan."  

I am not sure why you are concerned about stratification. The formula you are using (summarized in a table format) is for estimating a population mean of 50% with a 5% degree of accuracy (in other words, there is a 95% chance that your estimate will fall between 45 and 55%).

If you want to determine how effectively your sample can detect statistical relationships, then you should do a "power analysis." and there are several calculators for doing this available on the internet.

I suggest that you first study references such as those I noted above, and do not use any online 'calculator' without knowing whether or not it actually addresses your needs.  

The Krejcie and Morgan sample size table that Girija cites is based on the same classic formulas used in Cochran's book.The goal in that approach is to determine the accuracy of an estimate for a value, typically a mean.

Estimating sample size through power calculations is a more recent approach, and is based on the ability of a statistical test to detect an effect with a given sample size, given the typical set of assumptions as you would put into any sample size calculation. 

Just as with Cochran's sample size formula, the formulas involved in power analysis can be directly implemented in online calculators. That makes it as easy as looking sample size up in a table, but it would still be wise to have a clear idea about the assumptions behind whichever set of formulas you use.

I would not consider power more recent.  Rather old from my point-of-view.  A little restrictive for survey statistics.   Both are based on standard errors though.  

Thompson is good, and the PSU online info, such as the link I provided.    

(Thompson, S.K.(2012), Sampling, 3rd ed, John Wiley & Sons.) 

Most online calculators seem to be for proportions, not means.   

Thank you everyone. I have adopted the random sampling method and followed the krecie Morgan. I could not however make sure the sample size for each stratum is equal due to the nature of the population itself.