Why is there the character 李 in 行李？ Pleco lists three meanings for the character 李：


plum tree
plum
a surname 


None seem related to luggage!
The comments have the right idea.「行李」originally referred to a kind of messenger sent to run an errand, extended to mean the act of delivering a message/running an errand, further extended to mean to travel, and then finally the items taken along a journey; luggage.

「李」was used as a phonetic loan for「理」since the Warring States period, and for whatever reason,「行李」became more popular than「行理」, which is now restricted to meaning messenger.