Align Note below table

Yet another option, which doesn't use explicit \parboxes or minipages, would be to use the threeparttable package (the para and flushleft options give the desired placement):

\documentclass[a4paper]{article}
\usepackage{booktabs}
\usepackage{threeparttable}

\begin{document}

\begin{table}
  \centering\footnotesize
  \caption{Descriptive statistics of total sample based on modified data set}
  \label{table:descrtotal}\medskip
  \begin{threeparttable}
  \begin{tabular}{lrrr}
    \toprule
    & \% E & n UE & n E \\
    \midrule
    No Denomination & 0.63 & 1425 & 2470 \\ 
    Buddhist & 0.70 & 312 & 731 \\ 
    Hindu & 0.24 & 482 & 149 \\ 
    Muslim & 0.23 & 3993 & 1185 \\ 
    Orthodox & 0.51 & 1574 & 1609 \\ 
    Other Christian groups & 0.53 & 697 & 779 \\ 
    Other Denominations & 0.53 & 294 & 326 \\ 
    Other Muslim groups & 0.14 & 1428 & 238 \\ 
    Protestant & 0.55 & 1214 & 1472 \\ 
    Roman Catholic & 0.56 & 2031 & 2550 \\ 
    \bottomrule
  \end{tabular}
  \begin{tablenotes}[para,flushleft]
  Note: Share of aliens employed (\% E), Number of aliens unemployed (n 
UE) and Number of aliens employed (n E).
  \end{tablenotes}
  \end{threeparttable}
\end{table}

\end{document}

EDIT: moving the \caption and \label commands inside the threeparttable environment will also adjust the width of the caption to match the one of the table.

I propose a different approach: set the table in a box, and append the note beneath it in a parbox of the same width. I've also used booktabs to make the table more pleasant

\documentclass[a4paper]{article}
\usepackage{booktabs}
\newsavebox{\tablebox}
\begin{document}
\begin{table}
\centering
\caption{Descriptive statistics of total sample based on modified data 
set}\label{table:descrtotal}
\medskip
\footnotesize
\begin{lrbox}{\tablebox}
\begin{tabular}{lrrr}
\toprule
 & \% E & n UE & n E\\
\midrule
No Denomination & 0.63 & 1425 & 2470\\ 
Buddhist & 0.70 & 312 & 731\\ 
Hindu & 0.24 & 482 & 149\\ 
Muslim & 0.23 & 3993 & 1185\\ 
Orthodox & 0.51 & 1574 & 1609\\ 
Other Christian groups & 0.53 & 697 & 779\\ 
Other Denominations & 0.53 & 294 & 326\\ 
Other Muslim groups & 0.14 & 1428 & 238\\ 
Protestant & 0.55 & 1214 & 1472\\ 
Roman Catholic & 0.56 & 2031 & 2550\\ 
\bottomrule
\end{tabular}
\end{lrbox}
\usebox{\tablebox}\\[1ex]
\parbox{\wd\tablebox}{Note: Share of aliens employed (\% E), Number of aliens unemployed (n 
UE) and Number of aliens employed (n E).}

\end{table}
\end{document}

Note that the center environment should not be used inside table (use \centering) and that the footnotesize environment does not exist. It's possible to use it, but in certain circumstances it might bite you. :-). A \tiny paragraph is very difficult to read.

Add your note as an additional row spanning all four columns via \multicolumn. Making longer texts break in tables is possible with a minipage. The downside is, however, that you have to guesstimate the width of your table (I put in 6.5cm).

\documentclass{article}
\begin{document}
\begin{table}
\centering
\caption{ Descriptive statistics of total sample based on modified data set}\label{table:descrtotal}
\footnotesize
\begin{tabular}{l|rrr}
\hline\hline
 & \% E & n UE & n E\\ \hline
No Denomination & 0.63 & 1425 & 2470\\ 
Buddhist & 0.70 & 312 & 731\\ 
Hindu & 0.24 & 482 & 149\\ 
Muslim & 0.23 & 3993 & 1185\\ 
Orthodox & 0.51 & 1574 & 1609\\ 
Other Christian groups & 0.53 & 697 & 779\\ 
Other Denominations & 0.53 & 294 & 326\\ 
Other Muslim groups & 0.14 & 1428 & 238\\ 
Protestant & 0.55 & 1214 & 1472\\ 
Roman Catholic & 0.56 & 2031 & 2550\\ 
\hline\hline
\multicolumn{4}{l}{%
  \begin{minipage}{6.5cm}%
    \tiny Note: Share of aliens employed (\% E), Number of aliens unemployed (n UE) and Number of aliens employed (n E).%
  \end{minipage}%
}\\
\end{tabular}
\end{table}
\end{document}

---

Edit: I doubt that it's good style, but you get nicer-looking spacing before the note if you add an empty line (~\\) before it:

  \begin{minipage}{6.5cm}~\\
    \tiny Note: ...

Does anybody by chance have a solution how to get the width of the table automatically for the minipage?

---

Edit2: Used \centering and \footnotesize, as suggested.