You need to find the ROS stack that the package is contained in. The easiest way to do this is to go to the wiki page, e.g. http://www.ros.org/wiki/motion_planning_msgs . You'll see in the navigation bar that it's part of 'arm_navigation', so the debian package is ros-electric-arm-navigation.
The next version of roslocate will also let you do this as well. If you need it now you can fetch it from:
https://code.ros.org/svn/ros/stacks/ros_release/trunk/rosinstall/scripts/roslocate
./roslocate describe motion_planning_msgs
Type: package
Stack: arm_navigation
Description: This package defines a set of general-purpose messages and services for motion planning and control. It includes messages that can be used to specify joint and cartesian trajectories, represent robot state and services to compute motion plans. It also includes a set of conversion methods that can be used to convert messages from one form to another.
URL: http://ros.org/wiki/motion_planning_msgs
Update:
Need to use --distro=electric to catch the issue that Kei notes in the comment:
./roslocate describe motion_planning_msgs --distro=electric
cannot locate information about motion_planning_msgs
