This time, however, choosing that option appeared to do nothing. Rather than a menu full of commands, I was given only the option "Add Apache Derby Nature" in the Apache Derby context menu, which is what I had previously selected. I tried several times to add the nature in this manner, but to no avail.
The fix turned out to be simple. After grepping the directory of another project where I had successfully used Derby, I found that the change should have been reflected in my project's .project file.
The fix: if the Apache Derby nature isn't correctly added to a project through the Apache Derby menu, it can be done manually by editing the .project file (which is in the root directory the project). This is an XML file.
Find the <natures> node and add this line:
Then, just save the file. Problem solved.