`beamer` weiß nicht, dass es den Zähler für Overlays sichern muss. Man kann das aber notfalls selbst erledigen:
\documentclass[xcolor={dvipsnames}]{beamer}
\usepackage{ngerman}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{fancybox}
\usepackage{pict2e}
\usepackage{lmodern}
\usepackage{array}
\usepackage{mathtools}
\usepackage{caption}
\usepackage{algpseudocode}
\usepackage[linesnumbered, vlined, german, ruled]{algorithm2e}
\newcounter{salgorithm}
\begin{document}
\begin{frame}
\frametitle{Greedy-Algorithmus}
\only<1>{\setcounter{salgorithm}{\value{algocf}}}
\only<2->{\setcounter{algocf}{\value{salgorithm}}}
\only<1>{\setcounter{salgorithm}{\value{algocf}}}% Am Anfang des ersten Overlays den aktuellen Zähler für Algorithmen sichern
\only<2->{\setcounter{algocf}{\value{salgorithm}}}% Am Anfang aller anderen Overlays den Zähler auf denselben Wert setzen, der am Anfang des ersten Overlays gültig war.
\begin{algorithm}[H]
\caption{test algorithmus}
\pause
\KwIn{rein}
\pause
\KwOut{raus}
\pause
step 1
step 2
step 3
\end{algorithm}
\end{frame}
\end{document}
Den Hilfszähler kannst Du immer wieder verwenden:
\documentclass[xcolor={dvipsnames}]{beamer}
\usepackage{ngerman}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{fancybox}
\usepackage{pict2e}
\usepackage{lmodern}
\usepackage{array}
\usepackage{mathtools}
\usepackage{caption}
\usepackage{algpseudocode}
\usepackage[linesnumbered, vlined, german, ruled]{algorithm2e}
\newcounter{salgorithm}
\begin{document}
\begin{frame}
\frametitle{Greedy-Algorithmus}
\only<1>{\setcounter{salgorithm}{\value{algocf}}}
\only<2->{\setcounter{algocf}{\value{salgorithm}}}
\begin{algorithm}[H]
\caption{test algorithmus}
\pause
\KwIn{rein}
\pause
\KwOut{raus}
\pause
step 1
step 2
step 3
\end{algorithm}
\end{frame}
\begin{frame}
\frametitle{Noch ein Algorithmus}
\only<1>{\setcounter{salgorithm}{\value{algocf}}}
\only<2->{\setcounter{algocf}{\value{salgorithm}}}
\begin{algorithm}[H]
\caption{second test algorithmus}
\pause
\KwIn{rein}
\pause
\KwOut{raus}
\pause
step 1
step 2
step 3
\end{algorithm}
\end{frame}
\end{document}
Solange nur ein einziger Algorithmus auf der Seite ist, würde auch das einfachere:
\documentclass[xcolor={dvipsnames}]{beamer}
\usepackage{ngerman}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{fancybox}
\usepackage{pict2e}
\usepackage{lmodern}
\usepackage{array}
\usepackage{mathtools}
\usepackage{caption}
\usepackage{algpseudocode}
\usepackage[linesnumbered, vlined, german, ruled]{algorithm2e}
\newcounter{salgorithm}
\begin{document}
\begin{frame}
\frametitle{Greedy-Algorithmus}
\only<2->{\addtocounter{algocf}{-1}}
\only<2->{\addtocounter{algocf}{-1}}% Am Anfang aller Overlays außer dem ersten, den Algorithmenzähler um ein verringern.
\begin{algorithm}[H]
\caption{test algorithmus}
\pause
\KwIn{rein}
\pause
\KwOut{raus}
\pause
step 1
step 2
step 3
\end{algorithm}
\end{frame}
\end{document}
Wenn ein Algorithmus nicht auf dem ersten, sondern erst einem späteren Overlay begonnen wird, muss man natürlich die `\only`-Anweisungen anpassen.