The "with me" in "I always carry my notebook with me" is used to emphasize that the notebook is always close to where you are. In contrast, if you said "I always carry my notebook in my backpack," and if your backpack isn't with you, then the notebook isn't with you.
You wouldn't say "I always carry my notebook with someone else" because it doesn't make sense that there is someone else who has a relationship with your notebook because you carry it. On the other hand, it would make sense to say "I always hold hands with my wife" because "holding hands" usually means with someone else.
You can omit the "with me," but then the relationship between you and the notebook is less specific.