First, you need to find out where your octave executable lives, and note the full path to it. On Linux or OS X, open your favorite terminal emulator and type which octave, and if it's in your $PATH variable it will print the full path to it (for example, /opt/local/bin/octave or something like that). If it's not in your path, or if you're on Windows, you'll have to search around a bit until you find octave or octave.exe, if you're on Windows.
Once you have the path, open Sublime and select Preferences -> Browse Packages..., which will open your Packages folder (surprisingly). Navigate to Packages/SublimeREPL/config/Octave and open the Main.sublime-menu file in Sublime - don't worry, it's just plain JSON. Go down to line 18 (or thereabouts) - it should say "cmd": ["octave", "-i"],. Change "octave" to "/full/path/to/octave", obviously replacing /full/path/to/ with the actual full path you noted earlier.
Save the file, and you should be all set. Tools -> SublimeREPL -> Octave should now open up an interactive session, just like running octave -i on the command line would do. You can use all of the usual SublimeREPL shortcuts to send code to the running REPL, or just use if for testing functions, code snippets, etc. 
Have fun!