В чем заключаются их различия на уровне реализации?
Насколько мне известно, зависимость применяется тогда, когда критичны изменения в интерфейсе зависимого класса, то есть переименуй его метод, и в зависящем классе, использующем этот метод, все рухнет. Исходя из этого, мне не понятно, в чем толк от ассоциации? Содержать ссылку в классе A на класс B и иметь табу на использование его интерфейса?

ассоциация - структурный элемент, обладает кратностью, статичностью
зависимость - может проявится, может не проявится, не обладает кратностью

В чем заключаются их различия на уровне реализации?

Если рассматривать связи между классами на уровне реализации различия таковы:
ассоциация -- поле;
зависимость -- временная переменная (параметр вызова операции или локальная переменная в её теле). Табу ассоциация не накладывает, просто указывает, что связь существует в течение периода времени, сравнимого с временем жизни объекта.