A while back I searched all over the Taiwan Railways website for a list of stations that allow you to transport a bike as luggage (as opposed to taking it on the train with you) without success. So the next time I was at the luggage center at Songshan Station, I asked if such a list existed, and the folks there showed me this very helpful board on the wall. I immediately snapped a picture of it with my phone. It doesn't matter whether you're sending the bike or picking it up, the list of stations is the same.
This is useful because not all stations accept luggage. One that particularly surprised me a couple months ago was Yangmei: you have to go up to Zhongli or down to Xinfeng if you want to send your bike from that area.
When I ride outside of Taipei, I almost always send my bike there the day before. It's incredibly cheap (NT$34 basic fee plus NT$1.14 per kilometer), especially if you use the normal luggage train (一般行李車) instead of the express (自強PP車, I think they call it). You don't have to take your bike apart or put it in a bag, you just have to take off all the stuff that might fall off, like lights, odometers, etc. My experience has been that they take good care of the bikes: I've never noticed any damage to mine after a dozen or more trips. You're supposed to pick up your bike within two days of its arrival, but if you don't, they only charge you NT$20 a day to leave it there.
For those who don't read Chinese, here's the list of stations going counterclockwise from Songshan: Songshan, Wanhua, Shulin, Yingge, Taoyuan, Zhongli, Xinfeng, Hsinchu, [mountain line] Zhunan, Miaoli, Taichung, [ocean line] Yuanli, Dajia, Qingshui, Shalu, [mountain and ocean lines merge] Zhanghua, Yuanlin, Tianzhong, Ershui, Linnei, Douliu, Dounan, Dalin, Jiayi, Xinying, Longtian, Shanhua, Tainan, Luzhu, Gangshan, Nanzi, Fengshan, Pingdong, Chaozhou, Linbian, Fangliao, [huge gap in the southeast], Taidong, Guanshan, Chishang, Yuli, Ruisui, Guangfu, Fenglin, Shoufeng, Ji'an, Hualien, Xincheng, Nan'ao, Dongao, New Suao, Luodong, Yilan, Toucheng, Shuangxi, Ruifang, Keelung, Qidu.
Note that Taipei Main Station does NOT take bikes as luggage. You have to go to Wanhua or Songshan.