Что нужно сделать, чтобы Navigation Drawer (боковое меню) показывалось на всех activity моего приложения?
Здравствуйте. Правильнее, конечно, использовать фрагменты.
Чтобы показывать менюшку в других Acitvity - в их onCreate инициализируйте менюку так же, как в основной Activity (как вариант, чтобы не дублировать код, отнаследовать все Activity от какой-то базовой, у которой в onCreate инициализируется меню). 
Теперь о том, почему так делать плохо. При нажатии на элементы меню, я так понимаю, вы будете переключать Activity (показывать разные Activity). При этом у вас менюшка не будет плавно убираться при клике на элемент, а будет резко выскакивать Activity. При реализации же на фрагментах, у вас при нажатии на элемент меню, боковое меню плавно будет закрываться и параллельно будет отображатья фрагмент (посмотрите как это сделано в приложении Google Play, потыкайте в элементы левой менюшки и поймете).
Переделка на фрагменты это не страшно, я могу скинуть вам простой проектик (в Android Studio), в котором это реализовано - сделаете по аналогии. Кстати, реализация с фрагментами прекрасно работает с библиотекой, которую я описал в статье на хабре.
UPD: выложил пример тут: https://github.com/tral/MaterialDrawerFragmentSample
Если вы прям во всех ваших активити хотите сделать меню, сделайте базовый класс с реализацией меню и наследуйте от него все ваши активити.