Why is my bash prompt getting bugged when I browse the history?

Use \[...\] around the parts of PS1 that have length 0. It helps bash to get the length of the prompt right. Even with this measure, your command line can get spoiled when using multibyte characters (at least mine does). Hitting Ctrl+L also helps in such cases (but clears the screen at the same time).

You need to make sure you are escaping all of the non-printable characters.

Good

PS1="\[\e[36m\]\W ⇨ \[\e[m\] "

Bad

PS1="\[\e[36m\]\W ⇨ [\e[m\] "