Millinocket is in Highlands_(Maine).
Fly, if you have your own airplane, for there is a local airport. There is also a float plane service off the Golden Road to the west, near Baxter State Park.
Shuttle, Several, including the hostel, will pick you up in Medway or Bangor if you fly or ride the bus to one of those.
I suppose you could paddle in on the Penobscot.
Drive or Walk.
Don't miss the view from Baxter Peak on Mount Katahdin, several miles west.
Ambajejus Boom House is nearby, as is the
Antique Snowmobile Museum
Plenty to do if you like the outdoors, including white water rafting, canoeing, kayaking, hiking, camping, hunting, fishing, peakbagging, ATVing, snowmobiling, cc skiing, snowshoeing.
Two grocery stores east of town, IGA and Hannaford. Also a Family Dollar here. Several smaller general stores around town. A couple of hardware stores.
Pelletier's Family Restaurant (higher prices) 
Chinese, there are 2 chinese restaurants here.
Pizza in the shopping center with Family Dollar
Appalachian Trail Cafe at 210 Penobscot Ave.
There's other places I've missed.
Water. It's good for you. (But filter it if you're in Baxter State Park).
Hotels, There are at least Five hotels there. See below. There are also several hotels/lodges/resorts to the west toward Baxter State Park. There are also several Bed and Breakfasts in town.
Katahdin Inn and Suites Right behind the Right Aid, next to Family Dollar.
Baxter Park Inn, not associated with Baxter State Park.
New England Outdoor Centers Lodge on lake Millinocket.
Pamola Motor Lodge
Ruthie's Hotel Terrace and Restaurant, looks more like a restaurant, but they do have rooms.
Campgrounds There are plenty out west of town toward Baxter State Park. A couple of those are on the Golden Road, which runs parallel and south of the state park road.
If you need contact via Internet, there is a public library at the corner of Hill Street and Maine Avenue. They have computers available for public use. I believe they also have free WIFI access.