Two-dimensional systems such as surfaces and molecular monolayers exhibit a multitude of intriguing phases and complex transitions. Ultrafast structural probing of such systems offers direct time-domain information on internal interactions and couplings to a substrate or bulk support. We have developed ultrafast low-energy electron diffraction and investigate in transmission the structural relaxation in a polymer/graphene bilayer system excited out of equilibrium. The laser-pump/electron-probe scheme resolves the ultrafast melting of a polymer superstructure consisting of folded-chain crystals registered to a free-standing graphene substrate. We extract the time scales of energy transfer across the bilayer interface, the loss of superstructure order, and the appearance of an amorphous phase with short-range correlations. The high surface sensitivity makes this experimental approach suitable for numerous problems in ultrafast surface science.