How do diacritical marks impact centering and overshooting?

I think the best way to proceed is to stop using \hline -- and, while you're at it, ditch all vertical bars -- and to use the line-drawing macros of the booktabs package. For the table at hand, \toprule and \bottomrule should be used.

If, for some reason, you simply must use vertical bars (and hence can't use \toprule and \bottomrule), I suggest you load the array package and set the length of \extrarowheight to something like 2pt or 3pt.

\documentclass{article}
\usepackage{array,booktabs}
\begin{document}

%% original form
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\"Ostersund & \AA m\aa l & Oxel\"osund & Alings\aa s & \'Orlaith & O\'O\"O\H{O}\\
\hline
\end{tabular}

\medskip
%% with rule-drawing macros of the booktabs package
\begin{tabular}{cccccc}
\toprule
\"Ostersund & \AA m\aa l & Oxel\"osund & Alings\aa s & \'Orlaith & O\'O\"O\H{O}\\
\bottomrule
\end{tabular}


\medskip
%% with \extrarowheight set to 3pt
\setlength\extrarowheight{3pt}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\"Ostersund & \AA m\aa l & Oxel\"osund & Alings\aa s & \'Orlaith & O\'O\"O\H{O}\\
\hline
\end{tabular}

\end{document}

The problem is not in diacritics, it is in LaTeX tables. You can give rows some vertical padding with the cellspace package, which ensure a minimal vertical distance between a cell and the above and below rules.

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{array, cellspace}
\setlength\cellspacetoplimit{3pt}
\setlength\cellspacebottomlimit{3pt}

\begin{document}

\begin{table}[!h]
\begin{tabular}{|*{6}{Sc|}}
\hline
\"Ostersund & \AA m\aa l & Oxel\"osund & Alings\aa s & \'Orlaith &O\'O\"O\H{O}\\
\hline
\end{tabular}
\end{table}

\end{document} 

Insert a large \strut.

\documentclass{article}
\begin{document}
\begin{table}[!h]
\begin{tabular}{|c|c|c|c|c|c|}
\hline
{\Large\strut}\"Ostersund & \AA m\aa l & Oxel\"osund & Alings\aa s & \'Orlaith &O\'O\"O\H{O}\\
\hline
\end{tabular}
\end{table}
\end{document}