You always start from the first and second law of thermodynamics, i.e.,
\mathrm{d}U=T \mathrm{d} S-p \mathrm{d} V+\mu \mathrm{d} N.
Here, U is the internal energy, T the temperature, S the entropy, p the pressure, V the volume, \mu the chemical potential, and N a (conserved!) particle-number like quantity. In nonrelativistic physics often you can take N as the particle number itself, while in non-relativistic physics usually there are only conserved charges like elecctric charge, net-baryon number, etc. Here, we just consider the case of one such particle-number like quantities and thus only one chemical potential. The generalization to more variables is straight forward.
The above equation shows that the "natural" independent variables for the internal energy are S, V, and N. Since by construction \mathrm{d} U is a total differential, you read off relations like
\left (\frac{\partial U}{\partial S} \right)_{V,N}=T.
Here, the variables listed in the subscript indicate which variables have to be kept constant when differentiating. It's pretty important in this business to keep track of what's left constant when taking partial derivatives of the various quantities. Since from U you can derive other quantities by taking partial derivatives one calls U a thermodynamical potential, and which other quantities you get by taking derivatives in the most straight-forward way is determined by what are the "natural" independent quantities to use as explained above.
Let's now look at the entropy. From the equation above we get
\mathrm{d} S=\frac{1}{T} \mathrm{d} U+\frac{p}{T} \mathrm{d} V-\frac{\mu}{T} \mathrm{d}N.
The "natural" independent variables to be used together with the entropy are thus U, V, and N, and the corresponding partial derivatives wrt. to one of these three variables (keeping precisely the other two fixed) are the coefficients in front of the differentials. Again we use the argument that S is a state variable and thus \mathrm{d} S is a total differential. For the following it's convenient to introduce new variables, namely
\beta=1/T, \quad \alpha=\mu/T.
Then we have
\mathrm{d} S=\beta \mathrm{d} U+\frac{p}{T} \mathrm{d} V -\alpha \mathrm{d} N.
With a Legendre transformation you define new quantities such that other variables become the "natural" independent variables. Let's start with the first example. You are supposed to find a Legendre transformation of S such that the natural quantities become (\beta,V,N). Now, for the enropy V and N are already natural variables, but not \beta, but we have the relation
\beta=\left (\frac{\partial S}{\partial U} \right )_{V,N}.
Now to make \beta a natural variable of another quantitiy, you simply have to define the new quantity as
X=S-\beta U
Then from the above given differential you have
\mathrm{d} X=\mathrm{d} S - \mathrm{d}(\beta U)=\mathrm{d} S - U \mathrm{d} \beta-\beta \mathrm{d}U = \frac{p}{T} \mathrm{d} V-\alpha \mathrm{d} N-U \mathrm{d} \beta.
Now obviously the natural variables for X are indeed (\beta,V,N).
As next step you want still a new quantity such that the natural variables are \beta,V,N. Now you read off the last equation
\left (\frac{\partial X}{\partial N} \right)_{\beta,V}=-\alpha.
Thus, by another Legendre transform you see that the searched quantity must be
\Omega=X+\alpha N=S-\beta U+\alpha N
since this leads to
\mathrm{d} \Omega=\frac{p}{T} \mathrm{d} V+N \mathrm{d} \alpha-U \mathrm{d} \beta.
That's the grand-canonical potential with the natural independent variables V, \quad \beta, \quad \alpha.
