在桌子上-on the (upper surface of the) table; *Here* '上' is different from 'above/over'.
在墙上-on the (surface of the) wall.
When you note something down in your notebook, we say '写/记录 在笔记本上' or '在笔记本上 写/记录'. Because we write/scribe/paint/draw on the *upper *surface* of the table/wall/notebook, so here '上' fits in.
Or you can rephrase '在桌子上' as '在桌子的上面'. And you'd better take '在...上' as a set phrase.