Low Earth Orbit (LEO) satellite communication is a promising approach to provide Internet connectivity to users in many remote areas. As videos are likely to account for majority of traffic in the LEO satellite network as in the rest of the Internet, we conduct the first exploration of video streaming in LEO satellite networks. Using measurement and simulation, we show the importance of handover strategy and bandwidth prediction algorithms in both single-user and multi-user scenarios. Motivated by these observations, we first develop a bandwidth prediction algorithm. Then we propose a set of novel algorithms to jointly select the satellite and video bitrate. Our algorithms include model predictive control, dynamic programming, and reinforcement learning-based approaches. We demonstrate the effectiveness of our algorithms using trace-driven simulation and emulation.