Mr.Genius1) Уточнение о "сервис будет работать в высоконагруженной системе" говорит о том, что алгоритм надо проработать настолько хорошо, чтобы не было узких мест?

Ну, как бы да. Но в данном тексте это скорее просто слова. Никто не пишет код с рассчетом что он будет не высокопроизводительным и не отказоустойчивым.

Mr.Genius2) Что значит кэшировать данные в памяти? Разве при определении переменных мы этого не делаем, выделяя участки памяти под переменные?

Вы правда не понимаете слова "кэшировать"? Есть код вашего сервиса, который реализует непосредственно решение проблемы.
Есть доступ к базе данных для обеспечения работы сервиса. Где-то между ними должен быть дополнительный слой хранения данных, который будет на много быстрее чем доступ к БД. Он будет хранить часто используемые данных, чтобы уменьшить число обращений к базе.

Mr.Genius3) При сохранении в БД (Oracle), я так понимаю, мы должны использовать пакет java.sql. Как мне это все смоделировать в домашних условиях? Пока что, только установил Oracle DB 11g XE, посоздавал простые таблички, но без использования джавы.

Google -> JDBC Tutorial

Mr.Genius4) "В качестве транспортного слоя можно выбрать любой из протоколов RMI, Hessian, HTTP" вообще не понятно что это и к чему?
Это значит что есть какой-то клиент, который будет обращаться к сервису по сети и обмениваться с ним данными по вышеуказаным протоколам. А сервис будет работать с БД, реализуя решение.