The Neutron Star Interior Composition Explorer (NICER) presents an exciting new capability for exploring the modulation properties of X-ray emitting neutron stars, including large area, low background, extremely precise absolute event time stamps, superb low-energy response and flexible scheduling. The Pulsation Searches and Multiwavelength Coordination working group has designed a 2.5 Ms observing program to search for emission and characterize the modulation properties of about 30 known or suspected neutron star sources across a number of source categories. A key early goal will be to search for pulsations from millisecond pulsars that might exhibit thermal pulsations from the surface suitable for pulse profile modeling to constrain the neutron star equation of state. In addition, we will search for pulsations from transitional millisecond pulsars, isolated neutron stars, low-mass X-ray binaries (LMXBs), accretion-powered millisecond pulsars, central compact objects and other sources. We present our science plan and initial results from the first months of the NICER mission, including the discovery of pulsations from the millisecond pulsar J1231-1411.