Mszep gave a very good answer; However I have some doubts if its in general true that entropy will increase with temperature(case 2 below), or (for an isolated system) with energy : -
Suppose $X$ is a given physical system. Here for definiteness we assume that microscopic description of $X$ is given in framework of quantum mechanics so that we have a simple definition of term "microstate" as an eigenvector of Hamiltonian $H$ of the system.
Case 1: Isolated system
If system is isolated and has energy $E$ then for computing entropy all that one need to do is work out following two steps :
find number of eigenstates $\Omega_E$ of $H$ corresponding to energy $E$.
Compute $S(E)$ as $S(E)=klog_e\Omega_E $.
If Hamiltonian of the system is such that $\Omega_E$ increases with $E$ then $S(E)$ will be an increasing function of $E$. But I am not sure if this condition of increasing $\Omega_E$ is always satisfied for all nontrivial many body physical Hamiltonians. Also it should be noted that there could be additional complications in that Hamiltonian itself may change with increase in energy. (e.g. as Mszep remarked, for an atomic system vibrational modes may come into play at higher energy; and so in this particular case more energetic system can be argued to have more microstates and hence more entropy)
Case 2: System in contact with a heat reservoir
When system is at some nonzero temperature $T$ then its total energy is not fixed, but we have a Boltzmann distribution of energies; and entropy is now given by following formula :
$S=-k\displaystyle\sum_i p_ilog_ep_i$
Here sum is over all microstates available to the system; and $p_i=exp(-E_i/kT)/Z(T)$, where $Z(T)=\sum exp(-E_i/kT)$ is partition function at temperature $T$.
Now to see if $S$ increases with temperature we need to compute its derivative wrt $T$ and check if its positive or not:
$\displaystyle\frac{dS}{dT}=-k\sum_i (\frac{dp_i}{dT}log_ep_i+\frac{dp_i}{dT}) $
Since net change in probability should be zero so $\displaystyle\sum_i\frac{dp_i}{dT}=0$.
So we are left with :
$\displaystyle\frac{dS}{dT}=-k\sum_i \frac{dp_i}{dT}log_ep_i \tag1$
$p_i$ tells probability and so should be less than 1, and so $log_ep_i$ should be less than (or equal to) zero for each $i$.
On the other hand,
$\displaystyle\frac{dp_i}{dT}=-\frac{1}{Z^2}\frac{dZ}{dT}exp(-E_i/kT)+\frac{E_i}{kT^2Z}exp(-E_i/kT)$.
and $\displaystyle\frac{dZ}{dT}=\frac{Z}{kT^2}<E>$ ($<E>$=expectation value of energy).
So $\displaystyle\frac{dp_i}{dT}=\frac{E_i-<E>}{kT^2Z}exp(-E_i/kT)\tag2$
This quantity is positive for states whose energy is greater than $<E>$ while its negative for states whose energy is less than $E$. Thus, to the extent this elementary analysis is valid, entropy may not necessarily increase with increase of temperature.
More calculations (Added on 09-05-13) :
Substituting (2) into (1) we get :
$\displaystyle\frac{dS}{dT}=-k\sum_i \frac{E_i-<E>}{kT^2}p_i log_ep_i $
$=-k\displaystyle\sum_i \frac{E_i-<E>}{kT^2}p_i log_ep_i$
$=-k\displaystyle\sum_i \frac{E_ip_i log_ep_i-<E>p_i log_ep_i}{kT^2}$
$=-k\displaystyle\sum_i \frac{E_ip_i (-\frac{E_i}{kT}-log_e Z)-<E>p_i (-\frac{E_i}{kT}-log_e Z)}{kT^2}$
$=-k\displaystyle \frac{ (-\frac{<E^2>}{kT}-<E>log_e Z)-<E> (-\frac{<E>}{kT}-log_e Z)}{kT^2}$
$=k\displaystyle \frac{ (\frac{<E^2>}{kT}+<E>log_e Z)-<E> (\frac{<E>}{kT}+log_e Z)}{kT^2}$
$=\displaystyle \frac{<E^2>-<E>^2}{kT^3}$
$=\displaystyle \frac{<(E_i-E)^2>}{kT^3}$
Thus for a system in equilibrium with another system at a (positive) temperature $T$ entropy will increase with increase in temperature.