The first thing the students will need to know is how to dissect a scripture reference like "John 3:16" into a book, chapter, and verse.
Next, the students will need to become familiar with the order of the books, or at least the general area of the Bible each book is in.
You mention that they will likely ignore the table of contents – I think it will be easier to teach them to use the table of contents starting out, than to teach them a fancy mnemonic technique for finding books.
As they use the table of contents over and over, they will start to remember which books are in the Old Testament, which are in the New Testament, and which ones are at the beginning, middle, or end of the list. Eventually, they will start flipping to an approximate location in the Bible without looking at the table of contents.
In addition to using the table of contents, memorization songs can be very helpful to get the specific order down and to remember smaller books that you may not visit as often. I used these songs growing up: The Books in the Old Testament; The Books in the New Testament. Unfortunately, the deuterocanonical books are not included, but there are a lot of variations online and I'll bet you could find something that does include them.