What you want to find is the standard deviation of the sampling distribution of the mean. I.e., in plain English, the sampling distribution is when you pick $n$ items from your population, add them together, and divide the sum by $n$. We than find the variance of this quantity and get the standard deviation by taking the square root of its variance.
So, let the items that you pick be represented by the random variables $X_i, 1\le i \le n$, each of them identically distributed with variance $\sigma^2$. They are independently sampled, so the variance of the sum is just the sum of the variances.
$$
\text{Var}\left(\sum_{i=1}^n X_i\right) = \sum_{i=1}^n\text{Var}\left(X_i\right) = \sum_{i=1}^n\sigma^2 = n\sigma^2
$$
Next we divide by $n$. We know in general that $\text{Var}(kY)=k^2 \text{Var}(Y)$, so putting $k=1/n$ we have
$$
\text{Var}\left(\frac{\sum_{i=1}^n X_i}{n}\right) = \frac{1}{n^2}
\text{Var}\left(\sum_{i=1}^n X_i\right) = \frac{1}{n^2} n\sigma^2 = \frac{\sigma^2}{n}
$$
Finally take the square root to get the standard deviation $\dfrac{\sigma}{\sqrt{n}}$. When the population standard deviation isn't available the sample standard deviation $s$ is used as an estimate, giving $\dfrac{s}{\sqrt{n}}$.
All of the above is true regardless of the distribution of the $X_i$s, but it begs the question of what do you actually want to do with the standard error? Typically you might want to construct confidence intervals, and it is then important assign a probability to constructing a confidence interval that contains the mean.
If your $X_i$s are normally distributed, this is easy, because then the sampling distribution is also normally distributed. You can say 68% of samples of the mean will lie within 1 standard error of the true mean, 95% will be within 2 standard errors, etc.
If you have a large enough sample (or a smaller sample and the $X_i$s are not too abnormal) then you can invoke the central limit theorem and say that the sampling distribution is approximately normally distributed, and your probability statements are also approximate.
A case in point is estimating a proportion $p$, where you draw $n$ items each from a Bernouilli distribution. The variance of each $X_i$ distribution is $p(1-p)$ and hence the standard error is $\sqrt{p(1-p)/n}$ (the proportion $p$ is estimated using the data). To then jump to saying that approximately some % of samples are within so many standard deviations of the mean, you need to understand when the sampling distribution is approximately normal. Repeatedly sampling from a Bernouilli distribution is the same as sampling from a Binomial distribution, and one common rule of thumb is to approximate only when $np$ and $n(1-p)$ are $\ge5$. (See wikipedia for a more in-depth discussion on approximating binomial with normal. See here for a worked example of standard errors with a proportion.)
If, on the other hand, your sampling distribution can't be approximated by a normal distribution, then the standard error is a lot less useful. For example, with a very skewed, asymmetric distribution you can't say that the same % of samples would be $\pm1$ standard deviation either side of the mean, and you might want to find a different way to associate probabilities with samples.