The most responsive and familiar mechanism is the physical D-Pad on the Xperia Play device; you could follow Mojang's example and target your game at that device. This would additionally provide support to any devices with a physical D-Pad, since the Play's D-Pad uses the standard D-Pad key codes. This includes trackballs like the one found on the Nexus One; for those devices you may want to provide an option to keep walking in the last direction they pressed until told otherwise.
If your goal is broad device compatibility, the equivalent would be a virtual joystick, since all Android devices are required to have a touch screen before they can install apps from the Android Market. If you're relying on a touch screen, however, I recommend you move the character to whichever point the user touches on the screen.
As Zoot mentioned in the comments, there is another option you may wish to support: bluetooth gamepads such as the iControlPad. That gamepad in particular maps the D-Pad controls to WASD key inputs, though others may vary.