One can show using Schrodinger equation that 
$$\frac{\partial}{\partial t} \langle\Psi(t)|\hat{A}|\Psi(t)\rangle = \frac{i}{\hbar}\langle\Psi(t)|[\hat{H}, \hat{A}]|\Psi(t)\rangle$$
where $\hat{A}$ is any time-independent operator. From this we have
$$[\hat{H}, \hat{A}] = 0 \Rightarrow \langle\Psi(t)|\hat{A}|\Psi(t)\rangle = Const.$$
I ask the opposite question: Lets say I chose some initial state $|\Psi\_0\rangle$ (not any) which is not an eigenstate of $\hat{H}$ and for which 
$$\langle\Psi(t)|\hat{A}|\Psi(t)\rangle = Const.$$
Does this implies that 
$$[\hat{H}, \hat{A}] = 0 ?$$

This is how we would start:
$$\langle\Psi\_0| e^{it\hat{H}} \hat{A} e^{-it\hat{H}}|\Psi\_0 \rangle = \sum\limits\_{k}|\alpha\_k|^2 \langle k | \hat{A} |k\rangle + \sum\limits\_{k,l,\\k\ne l}\alpha\_k^\* \alpha\_l \langle k | \hat{A} |l\rangle e^{-it(k-l)}$$
where $|\Psi\_0\rangle = \sum\limits\_k \alpha\_k |k\rangle$ is the decomposition of the state in the eigenbasis of $\hat{H}$.