In this study, highly sensitive hydrogen micro gas sensors of the multi-layer and micro-heater type were designed and fabricated using the micro electro mechanical system (MEMS) process and palladium catalytic metal. The dimensions of the fabricated hydrogen gas sensor were about $5mm{ imes}4mm$ and the sensing layer of palladium metal was deposited in the middle of the device. The sensing palladium films were modified to be nano-honeycomb and nano-hemisphere structures using an anodic aluminum oxide (AAO) template and nano-sized polystyrene beads, respectively. The sensitivities (Rs), which are the ratio of the relative resistance were significantly improved and reached levels of 0.783% and 1.045 % with 2,000 ppm H2 at $70^{circ}C$ for nano-honeycomb and nano-hemisphere structured Pd films, respectively, on the other hand, the sensitivity was 0.638% for the plain Pd thin film. The improvement of sensitivities for the nano-honeycomb and nano-hemisphere structured Pd films with respect to the plain Pd-thin film was thought to be due to the nanoporous surface topographies of AAO and nano-sized polystyrene beads.