You need to use \caption before \label; otherwise, the string picked for the reference will be the last one where an anchor was set (typically the one of a sectional unit), in this case, the one from \chapter. Here's a modified version of your code showing the desired result:
\documentclass[11pt, letterpaper]{book}
\renewcommand{\thechapter}{\Roman{chapter}}
\renewcommand{\thesection}{\arabic{section}}
\usepackage[chapter]{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\renewcommand{\thealgorithm}{\arabic{chapter}.\arabic{algorithm}}
\begin{document}
\chapter{First Chapter}
\begin{algorithm}
\begin{algorithmic}[1]
\State Some code here
\end{algorithmic}
\caption{A test algorithm}
\label{alg:algorithm1}
\end{algorithm}
Algorithm~\ref{alg:algorithm1} states blah blah blah and algorithm~\ref{alg:algorithm2} states blah blah blah.
\begin{algorithm}
\begin{algorithmic}[1]
\State Some code here
\end{algorithmic}
\caption{Another test algorithm}
\label{alg:algorithm2}
\end{algorithm}
\end{document}

If you don't want to give explicit captions to your algorithms, you can use the \phantomcaption command from the caption package (this, however, could be confusing since you are referencing by number some objects which aren't really numbered):
\documentclass[11pt, letterpaper]{book}
\usepackage{caption}
\renewcommand{\thechapter}{\Roman{chapter}}
\renewcommand{\thesection}{\arabic{section}}
\usepackage[chapter]{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\renewcommand{\thealgorithm}{\arabic{chapter}.\arabic{algorithm}}
\begin{document}
\chapter{First Chapter}
\begin{algorithm}
\begin{algorithmic}[1]
\State Some code here
\end{algorithmic}
\phantomcaption
\label{alg:algorithm1}
\end{algorithm}
Algorithm~\ref{alg:algorithm1} states blah blah blah and algorithm~\ref{alg:algorithm2} states blah blah blah.
\begin{algorithm}
\begin{algorithmic}[1]
\State Some code here
\end{algorithmic}
\phantomcaption
\label{alg:algorithm2}
\end{algorithm}
\end{document}
