The Open With submenu lets you temporarily override the default application for opening a file. For example, perhaps you normally open PDF files using Preview, but in a particular circumstance you want to use Adobe Reader instead. To do this, select the file and choose Open With ‣ Adobe Reader from the Record menu or the contextual menu.
The Always Open With submenu lets you change the default application for all files of a particular content type (UTI). For example, perhaps you want all your HTML files to open in BBEdit when double-clicked.
To change the default application for a particular file, use the Reveal in Finder command, then choose Get Info from the Finder’s File menu and look in the Open with section of the info window.