How to position an element relative to an anchor?

You can use xshift:

\documentclass{article}
\usepackage{tikz}
\begin{document}

    \begin{tikzpicture}[mybox/.style={rectangle, draw, minimum width=10mm, minimum height=10mm}]
    \foreach \addr/\val [count=\x] in {$0$,$1$/$28$,$6$/$\infty$,$6$/$\infty$,$6$/$25$,$0$,$6$/$\infty$} {
        \node (node\x) [mybox] at (\x,0) {\addr};
        \node[above=5mm] at (\x,0) {\footnotesize \x};
        \node[below=5mm] at (\x,0) {\val};
    }
    \node at ([xshift=-10]node1.south west) [below=5mm] {Edge Weight:};
    \draw[ultra thick] (node1.south west) rectangle (node7.north east);
    \end{tikzpicture}

\end{document}

With this small tweak your code produces:

For what it's worth, to make the code easier to read I would replace the for-loop with

    \foreach \addr/\val [count=\x] in {0,1/28,6/\infty,6/\infty,6/25,0,6/\infty} {
        \node (node\x) [mybox] at (\x,0) {$\addr$};
        \node[above=5mm] at (\x,0) {\footnotesize \x};
        \node[below=5mm] at (\x,0) {$\val$};
    }

If you want to use the calc library, you need to write your node operation as:

 \node at ($(node1.south west)+(-1,0)$) 

and you'll have:

Full code:

\documentclass[border=10pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{calc}
\begin{document}
\begin{tikzpicture}[mybox/.style={rectangle, draw, minimum width=10mm, minimum height=10mm}]
    \foreach \addr/\val [count=\x] in {$0$,$1$/$28$,$6$/$\infty$,$6$/$\infty$,$6$/$25$,$0$,$6$/$\infty$} {
        \node (node\x) [mybox] at (\x,0) {\addr};
        \node[above=5mm] at (\x,0) {\footnotesize \x};
        \node[below=5mm] at (\x,0) {\val};
    }
    \node at ($(node1.south west)+(-1,0)$) [below=5mm] {Edge Weight:};
    \draw[ultra thick] (node1.south west) rectangle (node7.north east);
\end{tikzpicture}
\end{document}