LAN matchmaking usually involves a broadcast socket, which is limited to a subnet. Or do direct connection to IP with a pre-determined port, if you know the DHCP-assigned IP of your phone (which should be behind the same NAT, so no public/private IP shenanigans).

If you turn on the SO_BROADCAST option on a UDP socket, and bind to a known port number, you can send and receive packets using the segment broadcast address (which is 255.255.255.255 for IPv4.)
You can then look for other programs that broadcast on whatever port you have bound. Hopefully, those will be your game, rather than some other program :-)
Using the recvfrom() function, you will receive the IP address of the host running that copy of the game, and you can talk directly to that program using that address (no need to broadcast once you've found it.)

Thus, a game server will typically "host" a game, and start broadcasting once a second a packet that starts with some known bytes (say, the name of your game) and information about the match (#players, map loaded, or whatnot.)
Clients will then listen for this packet, and when it comes in, add that possible match to the list of available games the user can choose from.
If a broadcast packet hasn't been received for a few seconds, the client UI should typically remove the match again, as that server is no longer broadcasting the availability of the match.

It really isn't complicated to be honest. If you're used to sockets, it's just a regular UDP broadcast version.

http://beej.us/guide/bgnet/output/html/singlepage/bgnet.html#broadcast

you can have a broadcast socket on the server, and regularly 'ping' the LAN (every few seconds) with packets containing the game server information (name, IP and/or port, number of players, or whatever you feel should be of interest to the clients). Clients listen to the pings, extract the game server information, and then can connect to the game server.

Or you can do the opposite, clients send pings through a broadcast socket, the server listens to client requests, and reply to the client with the game server information. In a small scale environment, it doesn't really matter which way you go.

Yes, if you use the Unity engine, then using the Unity network library will likely work okay for you.
Make sure you read the overview and understand what it can, and cannot, do for you out of the box, and if you need something it doesn't do, make sure you actually know how to extend it, or you may run into surprised.